# Weighted Uniform Strings

# Weighted Uniform Strings

kasatky + 16 comments C++

int main(){ string s; cin >> s; int n; cin >> n; vector<bool> vb(10*1000*1000); int mul=1; char prev='1'; for(int j=0; j<s.size(); j++){ int w = s[j]-'a'+1; if(s[j]==prev) {mul++; w*=mul;} else mul=1; prev = s[j]; vb[w] = true; } for(int a0 = 0; a0 < n; a0++){ int x; cin >> x; if(vb[x]) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }

rohit_thapliyal + 1 comment I'm a bit new to STL and stuff. Can you explain me what is this vector?

kasatky + 0 comments This vector contains the prepared answer YES or NO. Using it, you can respond to a large number of queries without performing a repetitive calculation.

sachinbisht939 + 1 comment Thank You. That is nice approach. Like the idea. :)

rohit_thapliyal + 0 comments [deleted]

Stephen26 + 0 comments great idea using bool,its like dynamically solving the problem without repeated calculations

badal_bokaro + 1 comment why is vb(10*1000*1000) used?

kasatky + 2 comments This is for clarity. Also acceptable:

vector<bool> vb((int)10e7);

PiyushArora1 + 0 comments Why do we require the size of array to be 10e7?

hiddencoder + 0 comments vector vb(string.size()*26);

PiyushArora1 + 2 comments Why do we require the size of the array to be 10e7?

jacusjoe + 4 comments This code may be easier to understand.... And is fairly efficient I would say

int main(){ string s; cin >> s; int n; cin >> n; vector <bool> a(10e7); for(int i=0;i<s.length();i++) //For every letter in the string {int sum=0; for(int j=0;j<s.length()-i,s[i]==s[i+j];j++) //Runs only as long as the next letter is the same sum+=s[i+j]-96; //Gets the weight a[sum]=true; //Every weight which is present is set as true at those indices } for(int a0 = 0; a0 < n; a0++) { int x; cin >> x; //Input required weight if(a[x]) cout << "Yes" << endl; //If the value at the index is true, that weight is present else cout << "No" << endl; } return 0; }

PiyushArora1 + 3 comments I'm asking why does the size of vector/array need to be 10e7?

EvenParity + 0 comments [deleted]jacusjoe + 2 comments Check out this portion of the problem statement (Input and Constraints)

Note this constraint:

0 <= x <= 10^7

10e7 is just another way to represent 10^7.

Now coming to what I was trying to accomplish with the vector:

The boolean vector has 10e7 indices. Let us take each index location of this vector to represent the corresponding weight of substring.

ie, If Index 5 of the vector is TRUE, then it means there is a substring of weight 5 somewhere in the string. If Index 100765 of the vector is TRUE, then it means there is a substring of weight 100765 somewhere in the string. If Index 153 remains false after running through the loop, it means there is no substring of weight 153 in the given string.

The constraints mentions that the string weight is in the range of 0 to 10e7. Hence the maximum possible weight that we would need to keep track of is 10e7. That's why I sized the vector to 10e7.

Sorry for the delay in clarifying... Hope you understood :)

PiyushArora1 + 0 comments Thanks! Actually I missed it in the problem statement.

leech932 + 0 comments There's no need for the array to contain 10^7 elements. The string can be at most 10^5 characters long, so the maximum possible uniform substring weight is 10^5 * 26 (a string of 100000 'z's). So you can size the array to 2600000 elements and add a simple check (xi must be less than 2600001).

praveen_dakshan1 + 0 comments **because sum may take larger value .**

mahak1 + 0 comments Amazing!

Madhuram_Kabra + 1 comment outer for loop can be made more efficient making

i=i+j

instead of

i++

iwith minor tweaks. Takes less time

anuradhasuthar31 + 0 comments [deleted]

Himanshu98 + 1 comment But here complexity may be more than O(n). Is it?

Madhuram_Kabra + 1 comment Yes it is more than O(n). But do these minor changes to make it linear...

for(int i=0;i<s.length();){ sum=0; int j; for(j=0;j<s.length()-i && s[i]==s[i+j];j++){ //find the weight of current substring sum+=s[i+j]-'a'+1; //make note of it. weight[sum]=true; } i=i+j; }

Himanshu98 + 0 comments okay, thanks for your kind support.

abhishek10pundi1 + 0 comments array size is 10e7 because of the constraint 1<=x<=10e7

upen12345 + 0 comments what if z is 10*1000*1000 times will it work??

billcrawford1970 + 1 comment You can do it with just a stored frequency for each letter (constant space, linear-ish time)

sidajwalia + 0 comments no. little bit change. not store frequency, bcz you will end storing max occurance of that char in string. what we need is length of continous substring, so better you store max length ( for continuous substring) for each char. and you will end up having linear time. not even lienr-ish. check this code.

static String[] weightedUniformStrings(String s, int[] queries) { s = s+"\0"; int[] char_num = new int[27]; int local_len = 1; for(int i = 1; i<s.length(); i++){ if(s.charAt(i) != s.charAt(i-1)){ char_num[s.charAt(i-1)-'a'+1] = Math.max(char_num[s.charAt(i-1)-'a'+1], local_len); local_len = 1; } else local_len++; } String[] ans = new String[queries.length]; for(int i = 0; i<queries.length; i++){ boolean flag = false; int j = 1; while(j<char_num.length){ if(char_num[j] > 0 && queries[i]%j == 0 && queries[i]/j <= char_num[j]){ ans[i] = "Yes"; flag = true; break; } j++; } if(!flag) ans[i] = "No"; } return ans; }

skji72 + 1 comment Why to use vector here instead of array since we know the max size we have to allocate;

kasatky + 1 comment Because the size of the vector< bool > is much smaller than the array of bool. In the vector, the bool takes 1 bit, in the array - 1 byte or more

hiddencoder + 0 comments BROTHER YOU CAN USE set<INT> WHY YOU ARE USE VECTOR<BOOL> INSTEAD OF set<INT>

HVTandon + 0 comments When we declare the bool vector, what is the initial data stored in its elements?

emailneer + 0 comments does this pass the test cases? you are comparing s[j] to prev, but the same character may not be placed adjacent eg - abcdbcdaasc

hiddencoder + 0 comments vector<bool> vb(string.size()*26); //sir this valid or not

rainald_koch + 0 comments You need to store only the length of the largest streak per character, that is, 26 numbers. Queries would be done with a loop over the weights and the divmod function, a modest overhead. Note that the 26-number table fits into the first-level cache (if not the register set), while your huge storage will cause L1 misses most of the time.

h150040646 + 1 comment Out of curiosity how much time did you take to solve this?

rainald_koch + 0 comments May be five minutes to read and analyze but an hour to code. I'm new to Python and do not skip a detour.

selva1996 + 0 comments its like counting sort.....using a vector of this huge size is it efficient??

prayag740 + 0 comments Nice Logic !! Thanks

alexdatavault + 0 comments quick python solution using one dictionary for non repeating weights of the substrings

def weightedUniformStrings(s, queries): t=s[0] acc=-(ord(t) - 96) tot={} for i in s: if i ==t: acc+=ord(i) - 96 tot[ord(i) - 96+acc if i != 0 else ord(i) - 96]=0 else: acc=0 tot[ord(i) - 96+acc]=0 t=i return ['Yes' if i in tot else 'No' for i in queries]

mrinalinishukla + 12 comments My Java Solution: Track continuous characters and reset the count on character change, use HashSet to improve performance for large strings.

public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.next(); int n = in.nextInt(); char [] charArray = s.toCharArray(); int contigentString = 1; int lastAlphaNum = 0; Set<Integer> numList = new HashSet<Integer>(); for(int i=0 ;i< charArray.length; i ++){ int alphaNum = charArray[i] -'a'+1; if(alphaNum == lastAlphaNum){ contigentString++; } else{ contigentString = 1; lastAlphaNum = alphaNum; } int num = (alphaNum) * contigentString; numList.add(num); } for(int a0 = 0; a0 < n; a0++){ int x = in.nextInt(); if(numList.contains(x) ){ System.out.println("Yes"); } else{ System.out.println("No"); } } }

reddroider + 3 comments I was using ArrayList instead of HashSet and it turned out that HashSet is much quicker. My code didn't pass some testcases with ArrayList.

RodneyShag + 5 comments Yes. An ArrayList has O(n) time to find an element if it's not sorted. You can find an element in O(log n) time if it's sorted (using binary search). A HashSet can find an element in O(1) time. I used a HashSet too.

mailforharry98 + 0 comments thank you bro....I was using Arraylist nd some cases were timed out but after using HashSet it passed all test cases. :)

g_souvik04 + 0 comments Thanks! I did not knew about this. I was doing it in C# (using List) and getting a timeout. Now I used HashSet and it works fine. I just had to change the List to HashSet. I will try reading further on this.

rufus17 + 0 comments Even HashSet cannot have duplicate elements. This is one of the significant advantage on using HashSet instead of ArrayList in this problem.

tuyh78451 + 0 comments Thank you for your nice comment!... I didn't know about it. :)

rishabh0_9 + 0 comments [deleted]

sayantan_dey_34 + 2 comments dude just use a binary search instead of list.contains().It will improve the searching time from O(n) to O(log n) and the remaining test cases will pass.

reddroider + 0 comments Using hashSet is easier than writing a binary search.

PortgasAce + 0 comments HashSet Contains() searches in constant time 0(1) not 0(n)

jasanign + 1 comment same here. I was using arraylist too. Instead of using HashSet, after taking a look at editorial, I figured out I could have replaced hashmap with hashset.

import java.util.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); //ArrayList<Integer> posW = new ArrayList<>(); Map<Integer, Integer> posW = new HashMap<>(); /** Map<Character, Integer> allW = new HashMap<>(); int counter = 0; for(char i = 'a'; i <= 'z'; i++){ allW.put(i, ++counter); } */ String s = in.next(); for(int i = 0; i < s.length();i++){ char temp = s.charAt(i); int counter = 1; posW.put((temp-96) * counter, 0); while(i+1 < s.length() && temp == s.charAt(i+1)){ i++; counter++; posW.put((temp-96) * counter,0); } } /* for(int i = 0; i < posW.size(); i++){ System.out.print(posW.get(i)+", "); } System.out.println(); */ int n = in.nextInt(); for(int a0 = 0; a0 < n; a0++){ int x = in.nextInt(); if(posW.containsKey(x)){ System.out.println("Yes"); } else { System.out.println("No"); } } } }

andadeacu + 0 comments What do you store in Map posW = new HashMap<>();?

Thanks bro.

kittugadu + 0 comments Had a similar solution but used strings. I like the use of ints to keep track of current string and count of them

nikhildbest12 + 0 comments Thankyou soo much for this solution. Because of you,I learnt about the concept of Hashset

saif01md + 1 comment you should use simple variable names.Its non-pronounciable.

KeyurPotdar + 0 comments public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.next(); int currentCharCount = 1; int lastAlphaNum = 0; Set<Integer> numList = new HashSet<Integer>(); for (int i = 0; i < s.length(); i++) { int alphaNum = s.charAt(i) - 96; if (alphaNum == lastAlphaNum) currentCharCount++; else { currentCharCount = 1; lastAlphaNum = alphaNum; } numList.add(alphaNum * currentCharCount); } int n = in.nextInt(); for(int a0 = 0; a0 < n; a0++){ int x = in.nextInt(); System.out.println(numList.contains(x) ? "Yes" : "No"); } }

KeyurPotdar + 1 comment Instead of converting string to array of char, use

*s.charAt(i)*. Wouldn't this be a bit efficient in terms of space?RodneyShag + 0 comments Yes it would.

Srajal + 0 comments Suggestion: In the first loop, if you first store the value of charArray.length in a variable and then iterate over this variable, its time complexity can be reduced from O(charArray.length^2) to O(charArray.length).

h1485237610 + 0 comments public class Solution { static char letter; static int weight; static void setLetter(char let) { letter = let; weight = let - 96; } public static BitSet buildBitSet(String s) { BitSet bs = new BitSet(); setLetter(s.charAt(0)); bs.set(weight); for (int i = 1; i < s.length(); i++) { char cur = s.charAt(i); if (cur == letter) { weight += (letter - 96); bs.set(weight); } else { setLetter(cur); bs.set(weight); } } return bs; } public static void main(String[] args) { BitSet bs = null; int[] a = null; try (Scanner in = new Scanner(System.in);) { bs = buildBitSet(in.next()); int n = in.nextInt(); a = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } } for(int i = 0; i < a.length; i++) { if(bs.get(a[i])) { System.out.println("Yes"); }else { System.out.println("No"); } } } }

andadeacu + 0 comments Can you say about num variable and alphaNum? alphaNum is a letter?

ankitayadav14411 + 0 comments I didnot know about hashset..so in this question it helped me in passing all test cases.

fopetkowicz + 0 comments Thanks man! I've been forgotten the Java utilities.

Mr_DarkSider + 0 comments [deleted]engg_priya01 + 0 comments Could you please help me with the lastAlphaNum variable you have used in the solution. Thanks in advance.

parth_bhoiwala + 4 comments My approach in Python using sets and dictionary for O(1) access.

alpha = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8, 'i':9, 'j':10, 'k':11, 'l':12, 'm':13, 'n':14, 'o':15, 'p':16, 'q':17, 'r':18, 's':19, 't':20, 'u':21, 'v':22, 'w':23, 'x':24, 'y':25, 'z':26} s = input().strip() n = int(input().strip()) scores = set() ctr=1 for i in range(len(s)): score = alpha[s[i]] ctr = ctr+1 if (i+1 != len(s) and s[i+1] == s[i]) else 1 scores.add(score*ctr) for a0 in range(n): x = int(input().strip()) print("Yes" if x in scores else "No")

jessachandler + 1 comment Great. I had tried a similar approach with a list using the strings library, like

`low = list(string.ascii_lowercase)`

, but it timed out. I'm going to have to look into why the dict was faster.sandeepsajan0 + 0 comments U can use ASCII value of char. but don't use list actually set is vastly faster. That is because the set uses a hash function to map to a bucket. time complexity of resizing O(1). but in list time complexity of resizing O(n).

mukeshbhakuni590 + 1 comment gives time out error

rmays + 1 comment This will give an error because you are assigning scores as the value from the dictionary corresponding to the appropriate key. To fix you can do the following to the for loop:

for i in range(len(s)): score.add(alpha[s[i]]) if (i+1 != len(s) and s[i+1] == s[i]): ctr += 1 else: ctr = 1 scores.add(score*ctr)

This will pass all the test cases.

wkcui + 0 comments I'm confused. What is the type of score? also set?

pappasbrent + 0 comments Thank you so much! That optimization was the last thing I needed

Anubhav_singh + 1 comment whats wrong in this???

import sys s = input().strip() n = int(input().strip()) list_=[] for x in set(s): for i in range(1,s.count(x)+1): list_.append((ord(x)-96)*i) for a0 in range(n): x = int(input().strip()) print( 'Yes' if x in list_ else 'No')

rainald_koch + 0 comments Using count is wrong, see "contiguous" in the description of the problem.

kegenrodrigues + 1 comment **Language: Python****Possible reason for Timeout Error**Appending to list was creating multiple repeated values.

Adding to set instead of appending to list solved my problem.

This is the only difference in both the codes i have provided.

Code With Timeout Error

#!/bin/python3 import sys s = input().strip() n = int(input().strip()) seq=[] for num in range(1,27): seq.append(0) for x in sorted(set(s)): i = 1; while x * i in s: i += 1 seq[ord(x)-97]=i-1 finale=[] #using list for index,every in enumerate(seq): for sval in range(every): finale.append((index+1)*(sval+1)) #using list for a0 in range(n): x = int(input().strip()) print("Yes" if x in finale else "No")

Code Without Timeout Error

#!/bin/python3 import sys s = input().strip() n = int(input().strip()) seq=[] for num in range(1,27): seq.append(0) for x in sorted(set(s)): i = 1; while x * i in s: i += 1 seq[ord(x)-97]=i-1 finale=set() #using set for index,every in enumerate(seq): for sval in range(every): finale.add((index+1)*(sval+1)) #using set for a0 in range(n): x = int(input().strip()) print("Yes" if x in finale else "No")

Hope it helps!

1stanleydsouza + 0 comments thanks mate :)

eforcework + 1 comment javascript solution:

// Complete the weightedUniformStrings function below. function weightedUniformStrings(s, queries) { var code; var prevChar; var prevCharCount; var dic = Object.create(null); for (var i = 0; i < s.length; i++) { code = s.charCodeAt(i) - 96; if (prevChar === code) { prevCharCount++; } else { prevCharCount = 1; prevChar = code; } dic[code * prevCharCount] = true; } var result = []; for (var i = 0; i < queries.length; i++) { result.push(dic[queries[i]] ? "Yes" : "No"); } return result; }

pratheep_my + 0 comments Awesome!

nraptis + 0 comments Swift:

import Foundation let inputString = readLine()! var input = Array(inputString.unicodeScalars.map { Int($0.value) }) for i in 0..<input.count { var c = input[i] let a = Int(UnicodeScalar("a").value) c -= a c += 1 input[i] = c } let queryCount = Int(readLine()!)! var maxSequence = [Int]() for i in 0..<26 { maxSequence.append(0) } var prevChar: Int = -1 var sequenceCount: Int = 0 for i in 0..<input.count { if prevChar == input[i] { sequenceCount += 1 } else { sequenceCount = 1 } if sequenceCount > maxSequence[input[i] - 1] { maxSequence[input[i] - 1] = sequenceCount } prevChar = input[i] } for _ in 0..<queryCount { var query = Int(readLine()!)! var collide = false var index: Int = 0 while index < maxSequence.count && collide == false { var val = maxSequence[index] if val > 0 { let num: Int = (index + 1) //num * X = query var expected = query / num if expected * num == query && expected <= val { collide = true } } index += 1 } print(collide ? "Yes" : "No") }

LaughDonor + 0 comments Anyone a fan of one-liners? Here's my uglified code (my solution breaks it up into more optimized parts.

weights = set(chain.from_iterable(imap(lambda (x, y): x * y, enumerate(g, 1)) for _, g in groupby(imap(lambda c: ord(c) - 96, raw_input())))) for X in (input() for _ in xrange(input())): print ["No", "Yes"][X in weights]

Basically it does the following:

- Generates the set of weights by:
- Mapping each character in S to it's value (a=1, b=2, etc..)
- Grouping consecutive values together
- Converting each group into a list of cumulative sums
- Flatten this list of lists into a single list, and removing duplicates

- Iterating through each query and checking if that value exists in the set.

- Generates the set of weights by:

code_point + 0 comments can someone let me know how to optimize this code below ?

public static void main(String[] args) { int i=0; Scanner in = new Scanner(System.in); String s = in.next(); int n = in.nextInt(); int sum=0; int num[]=new int[n]; for(int a0 = 0; a0 < n; a0++) num[a0]=in.nextInt(); for(int k=0;k<n;k++) { sum=s.charAt(0)-'a'+1; if(sum==num[k]) { System.out.println("Yes"); continue; } for(i=0;(i+1)<s.length();i++) { if(s.charAt(i)==s.charAt(i+1)) { sum+=s.charAt(i)-'a'+1; } else sum=s.charAt(i+1)-'a'+1; if(sum==num[k]) { System.out.println("Yes"); break; } } if((i+1)==s.length()) System.out.println("No"); } }

devinludwig + 2 comments ruby:

require 'set' map, weights, counter = ('a'..'z').zip(1..26).to_h, Set.new, 1 s = gets.strip.chars.map{|c| map[c]} for i in 0...s.length counter = (i > 0 and s[i] == s[i-1]) ? counter + 1 : 1 weights.add counter * s[i] end gets.strip.to_i.times do puts weights.include?(gets.strip.to_i) ? "Yes" : "No" end

andrewpatterson + 2 comments I'm learning about sets in Ruby, and I was wondering how do you know when to use a Set vs an array? Does using a set to store the weighted substring values make the .include? method faster?

devinludwig + 0 comments yes, as far as i've read it makes the include? search 0(1) instead of 0(n). It's my first time using a set, but it seems like it would be faster any time order doesn't matter (and count doesn't matter since it seems to only hold unique elements.)

pratergc + 0 comments Set implementations in all languages (that I know of) are hash tables, which does make lookup O(1) in the average case. The reason for this is that the memory allocated for the hash is indexed by the hash of the objects, so all the program has to do to know if the set contains an element is to generate the hash of that element and then jump directly to that location in memory (barring any collisions) and check if anything is there. For an array, the elements are not ordered in this way so the language has to iterate through (on average) half of the elements in the array if it contains the element and all of them if it doesn't. This is the reason hash lookups are faster. The downside is they require much more memory to store than an array, which is packed bytes.

daft_leech + 1 comment My ruby vers. i used hashes

s,v = gets.strip.scan(/((\w)\2*)/).map(&:first), {} s.each{|a| a.scan(/\w/).each_with_index{|b,i| v[(('a'..'z').to_a.index(b)+1)*(i+1)] = 0}} gets.strip.to_i.times{puts v[gets.strip.to_i]!=nil ? "Yes" : "No"}

Nyamath + 0 comments import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.next(); int n = in.nextInt(); int val[] = new int[n]; for(int a0 = 0; a0 < n; a0++){ int x = in.nextInt(); // your code goes here val[a0] = x; } int result = 0; int temp = 0; Set<Integer> arr = new HashSet<Integer>(); for(int i=0;i<s.length();i++) { if(i>0 && s.charAt(i-1) == s.charAt(i)) { temp = temp + s.charAt(i) - 97 + 1; result = temp; } else { result = s.charAt(i) - 97 + 1; temp = result; } arr.add(result); result = 0; } for(int i=0;i<n;i++) { if (arr.contains(val[i])) System.out.println("Yes"); else System.out.println("No"); } }`

}

speroh + 5 comments Simple O(n) in python

#!/bin/python3 import sys s = input().strip() n = int(input().strip()) sorted(s) a_set = set() prev = '' count = 0 for c in s: if c != prev: count = 1 prev = c else: count +=1 a_set.add(count * (ord(c) - 96)) for a0 in range(n): x = int(input().strip()) print("Yes" if x in a_set else "No")

janavarun12 + 0 comments [deleted]janavarun12 + 1 comment could you pass all test cases with this soln?

LaughDonor + 0 comments [deleted]

mdakan + 1 comment I'm not sure about the step where you sort s, for two reasons.

- This brings the runtime up to O(x*log(x)), where x = |s|.
- The problem specifies contiguous substrings. Sorting would create longer uniform strings in some cases (ex. s = 'aca', x_i = 2) that shouldn't be in the set of weights.

Is there something I'm missing? Maybe the test cases don't have long enough strings or ones like the example I gave.

LaughDonor + 1 comment Oh you're right about that. The string shouldn't be sorted because of how the problem was designed.

mdakan + 1 comment Weird, looks like this still passes all test cases. Something like these two should be added:

# This should fail by answering Yes instead of No aca 1 2 # This should time out, with |s| = 10**5 sdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxzasdfghjklqwertyuiopmnbvcxza... 100000 1 2 3 # etc for 10**5 queries

pratergc + 0 comments sorted() just returns the sorted list, it doesn't modify the original list. So in his code, that line did absolutely nothing.

scandium + 1 comment Can u please tell me the difference ?? Mine one is getting timeout error in some test cases .

a=raw_input() b=int(raw_input()) solvec=[] solvec.append((ord(a[0]))-96) count=1 for i in range (1,len(a),1): if a[i]==a[i-1]: count=count+1 solvec.append((ord(a[i])-96)*count) else : count=1 solvec.append(ord(a[i])-96) for i in range (b): c=int(raw_input()) if c in solvec: print "Yes" else : print "No"

mdakan + 1 comment You're using a list as the data structure to store the values present in the string (

`solvec`

), and then iterating over it repeatedly in the second for loop. This makes the run time O(n**2).I'd recommend reviewing the differences between sets and lists, and maybe implementing a set yourself to really understand it. The goal is to understand why each of these operations are the given complexity.

scandium + 1 comment Thanks . That really helped a lot . So basically , here , "set" is more appropriate than "list" and iteration is quit faster over the "set" .

mdakan + 0 comments That's right. The key difference is that you can check if something is in a set without iterating over everything in it.

`if c in x`

is O(n) if x is a list, but O(1) if x is a set.

wanghaitang_ufl + 0 comments [deleted]

Sort 314 Discussions, By:

Please Login in order to post a comment