I once had an interview with this company called ViaSat. I literally only studied 1 coding question the night before and it was this one. Out of pure coincidence, the whiteboard question they asked me to do was this one (the only question I had studied.)
yeah exactly, doesn't seem like a good solution. I would use some kind of structure to keep track of the first encountered position of each character as well as the total count, and you can use that after parsing the string to quickly find the first one, that's O(n)
the complexity of the solution as presented in code is really O(n^2) but the idea can be coded in O(26*n) (i.e. O(n)) if the outer for loops through the set of 26 possible symbols rather than through the input and records the minimum symbol-indexOf pair. Actually it is a nice representation of the solution with functional/logical programming properties, a version of looking for minimum element. Of course the problem can be solved in a single pass, so if really striving for time efficiency, even two passes are two much, more so 26.
Another way to think of using an array indexed by each letter’s place in the alphabet is that this is still a hash map. You are deriving the location in memory of each piece of data by using a key’s hash - it’s just that you have a closed set of keys, so you can have an incredibly simple hashing function.
What about LinkedHashMap? They are sorted the way in which you are entering the key-value pair, so we can go with a for-loop in the end just to find the first key that has value 1.
I came here to see if anyone mentioned this. If you're going to use a HashMap anyway then you might as well use a LinkedHashMap and then iterate through that to find the first with a count of 1.
@@mammlouk Yeah exactly, in general it's better to just use LinkedHashMap over HashMap, just because in the end you know where each element is. And this example here is just perfect for LinkedHasMap.
That's the solution I came up with. I used a LinkedHashMap to keep track of entries and a boolean array to mark bad characters. When coupled with streams, you can filter as you're going through the character array and remove items from the map. Then at the end it's just testing if the map is empty or picking off the first key.
There is one problem with your solutions. For the 26 long array solution, what happens if you give it the input “fall”? ‘a’ will be 1 and ‘f’ to 1, looping through afterwards gives us ‘a’ as the first non repeating character, but what we actually wanted was ‘f’. For the first hash-map solution, there are some different implementations which can also affect the order of the keys, which in turn makes the looping through to get the one with count 1 unpredictable and may yield false results.
Great video bro... Just a doubt isn't the last solution O(n^2) because maybe .indexOf() and .lastIndexOf() has O(n) complexity internally and we are iterating through the array therefore O(n^2) ???
The indexOf and lastIndexOf implementation, the cost is N^2, because the implementation of this function it's a loop so it will be a loop inside a loop -> n^2
Really depends on the language. Since the array doesn't change after the first lookup it will act as a dictionary and spit out indexes without going through the array.
Even though time complexity doesn't change, you can still lower the constant by storing the position of the first encounter of the letter, it would change from O(2n) to O(n+26) which on large strings is faster
The array could store 0 for not encountered, index (starting at 1) if encountered once, and then -1 if encountered more than once. Then just scan the array for the lowest value and remember that index. The only states that need to be remembered are not seen, seen once, or seen more than once. Only seen once needs the index. Thus the other two states can be single integer values different from a valid index.
@@starskiiguy1489 My point was about representation, and thinking about when the location is even required. There is some practical value to not having multiple structures you have to manage separately, and having less redundant state. I think it's useful to be able to explore various ways of implementing things, looking at each from multiple angles.
i would use a linked list, an array of 26, and a counter for duplicated letters. every time the count for a letter changes from 0 to 1, push the letter onto the end of the linked list, change the array[char] from 0 to 1. Every time the count for a letter changes from 1 to 2, scan the linked list for the letter and remove it, change the array[char] from 1 to 2. and increment the counter. Do not do anything for any count changes. if the counter reaches 26 before the end of the input string, return "_" immediately. otherwise, return the first element of the linked list when you reach the end of the string. The time complexity is O(n) for scanning input string, plus O(1) for pushing to linked list, plus O(1) for scanning linked list for removal because maximum is 26, plus O(1) for array access. Time complexity is O(n + c) = O(n)where c < n for n > 26. whereas if you do the hash table and scan you will have O(2n) = O(n), because the unique letter might be at the end so you will have to scan the entire string twice
I agree, this way you only really do 1 loop around the string. Another way is to use split and count the length of the resulting arrays hence if the length is 2 then you have your unique character.
@@fidelischarles4545 But the creator of this video kept counting after 2. If the string is long or contains a lot of the same character, we waste some time. Skipping a character would be rewarding. Is there an actual reason to do so?
@@LenaUA-cam Well, to skip the character you first have to check if it's already marked. In a complex data structure, just to find one number can take a whole algorithm. At the best it is going to be O(1) time which is the same if not skipping it. In case we were finding all the unique numbers I guess a splitting array makes sense.
How does that handle abbbbcddddddeeeeeefffa ? I would use a 2nd map (array or hash) to keep track of position of characters with a count of 1 (remove when it exceeds). At end loop through that 2nd map which is O of the cardinality of the char set (which is constant)
A simple optimisation for the double for loop: initiate j as i+1, since there’s no point repeating earlier characters that have already been tested and are known to be repeating
from the thumbnail i thought this was a trick question as they asked you which character is the first non repeating character and the first a is because there were no a's before that a
you can have an ordinal value starting at 1. instead of storing the count in the hash, you store the ordinal the first time (and increase the ordinal by one), if there was an ordinal already, set it to -1. Then after you finish the array once, you just search the hash for the item with the minimum positive value. That's your 1st non repeated. Instead of O(2n) you have O(n+26) = O(n) which is better specially for big arrays.
When I first attempted this I differentiated grammatically between the meanings of 'repeating' and 'repeated'. 'Repeating' I inferred as coming up next to again and again etc i.e. n instances of the same character adjacent to each other, whereas 'repeated' was what I inferred that the question is actually asking for i.e. is repeated elsewhere in the string. Semantics maybe, but don't get caught out folks like I did :)
You could also start at the back and keep a list of all chatacters found. Then every time you find a character you haven't yet seen, you store that as your candidate. The last one standing is the one. Edit: I suppose that you would have to search the string as much as you search the hash table. If not one time less since you don't have to do it at the end.
it would be ~O(26n) instead of ~O(2N) since you go through a 26 char array N times. it would actually be faster to dummily increment each value in some sort of ordered hashmap and search after for count==1.
Here’s my solution, i believe it only takes a single for loop (O(n)): - Start at the end of the string, iterate backward - Keep a hash map as in the video with the number of occurrences - Also keep a single character which represents the last encountered letter - In the loop: 1. If the character has been seen already (hash map not zero) add 1 and continue 2. Of the character has NOT been seen already (hash map is zero) add 1, update the “last seen” character, and continue - This way, we skip all the repeated characters once they are logged - Once we get to the end of the loop, if the count of the “last seen” character is 1, then return that character (I.e. it was unique and closest to the start) otherwise return underscore Amazon pls hire me for all your weird string filtering needs
That is the correct answer, although it wouldn't matter if you went forwards or backwards. You could also hash more information about the different locations, number of iterations when to break. and so on.
This is an incorrect solution. It would fail, for example, on case “aaabbaac”, returning b instead of c. The best case scenario is O(2n) no matter what, and I’m too tired to write out why right now. Ping me later to hear an explanation.
@@jajefan123456789 too long i didnt read his solution fully. But I feel this was his idea. It will return c because it was the last character with count = 1 pseudocode dic = {} lastCharWithCountOfOne = " " for(end, beginning): dic[character] += 1 if dic[character] == 1: lastCharWithCountOfOne = character if lastCharWithCountOfOne != " " : return lastCharWithCountOfOne else: return "_"
This doesn't work. It cannot keep track of the correct last seen unique character in a single variable. Just take the Wendell Wu example: "aaabbaac". At first the variable is c. Then it will instantly change to a, because it is the first occurence of that letter. It doesnt know that there will be more a's. So already we have lost the correct letter, which was c. Then it will update to b, and at the end it wont even return that, because it wasnt unique, it will return underscore, which is wrong.
You don't actually need a hashmap. Just create a bit vector associated with the character's ascii value. You don't care how many times it happens, just update a single bit. It will be almost constant time/space since you only need 56 bits to represent the entire a-zA-Z alphabet.
I thought exactly the same, but the only thing you have solved is which letters of the alphabet have a representation in the string and which of them appear more than once, hence lacking the knowledge of which is the first letter that appears only once. To solve this, you can XOR both vectors and loop through the string again, when you access such XOR'd vector and find a 1/True, you found the first non-repeating letter. It is O(2*N) which simplifies into O(N). You can check if the XOR gave 0 before looping to know if there were no letters satisfying the criteria. It is worse than other implementations but it is the least memory-hungry one. Only 2 long int to save all that information (plus whatever pointer/index you use to loop).
I find myself tempted to use recursion here: // Find the first non-repeating character in a string // Returns null for empty strings and strings with no unique chars function findFirstNonRepeatingChar(str) { // Get the first character of the string let char = str.charAt(0) if(!char) return null; // Replace all instances of that character let repl = str.split(char).join('') // Recurse if you replaced more than one character if(str.length - repl.length > 1) { return findFirstNonRepeatingChar(repl) } else return char }
Thankfully the stack depth won't be fucked but can you tell me O(what) this is? (time and memory) You need to have this skill at the interview (I stopped myself from giving you the answer).
@@paulstelian97 That's a good point... The worst case would be all duplicate characters, so I guess it would be O(n * k), where n is the length of the string and k is the number of unique characters (max 26). There are only 26 letters in the question, so it's a maximum stack depth of 26, and the string shrinks by at least 2 until an answer is found... That said, you make a good point. Recursion makes the code easier, but it takes way more memory/stack space than a simple loop.
@@Krechevskoy Sure. Since k is limited by 26 you may as well replace it by 26 (big-O shows the worst case indeed) which disappears as O(c * n) = O(n). So it is linear time, and I'm not sure what to understand of what you said from the memory point of view (the correct answer is also linear for the same reason)
@@paulstelian97 Yes, the memory is also linear, but it is also worse than a simple loop because of the recursion. Each stack frame needs to hold a (shorter) copy of the string, which is the typical downfall of recursive functions.
Another more mathematical solution could be assigning each letter a prime number and using a for loop multiplying each prime number associated to the corresponding character, after that with other loop you start from left to right checking the reminder of dividing that result by the corresponding prime squared (with the operator %) if the answer is different than cero you return that character. Sorry for bad English, please ask if you have any doubts.
@@blazejeczek8710 for example, with the string abbcdda you get 2*3*3*5*7*7*2=8820 which can be divided by 2^2, 3^2, 7^2, the only prime squared in the list that cannot divide that is 25=5^2, so the result should be c.
@@sabazillo yea that is a clever solution in mathematical sense and it reminds me of a concept called hashing that can be used in other string/text problems (don't know if you are familiar with it): Basically you do what you've talked about - choose a prime number for each character and multiply it and you add an additional step which is moduling each time by a choosen number, preferably a big prime like 10^9+7 (you don't ever overflow). This way you can easily check whether 2 strings are composed of the same number of the same characters. Example: you know that "aabbc" is the same as "abcab" because it has the same hash value. But in this problem I think other solutions might be better due to the overflow issue.
Jack haters gonna hate. My laptop is above 1k. I brought UA-cam premium to watch this channel. I guess he’s gonna call me poor still. Just ignore him.I rather think he’s pathetic and feel a little sorry for him born in a bad family.I lift five times a week and keep myself lean all the time. If he hustles like we do he doesn’t got time to hate.I’ve reported him.
The third method using built in functions is dangerous, especially in an interview. It assumes that the built in function isnt bigger than polynomial. Your code code be constant time and the functions could be exponential. Whether it is or isnt, really isnt the problem, but before you opt to use it, be prepared to explain what its doing. Last but not least, a function call creates overhead, and doing a function call on each element will slow you down as the set grows. If you're trying shave off cycles, it's definitely a poor approach to call two function calls.
I like the last one. My solution was to take each letter in sequence, and then compare the string length, to the string length with that letter removed. If the result is 1 then you have the first non repeating letter, if not, use the string that has that letter stripped as the new input, and repeat until you get 1 as the difference in string lengths.
The last one in video doesn't work for the case there is no single occurance character, it'll print the last instance of any repeating character. Your solution works tho
@@HeyItsSahilSoni How does it not work? .indexOf always returns the first index of the item and .lastIndexOf always returns the last index of the item. If they are not equal the function returns "-". It will not return the last instance of a repeating character.
i'm not sure but i think that there is a way simpler thing to do. convert the string to byte array then a for loop and at each iteration get the character in the array and verify if the character before and after is the same if not it's the first non repeating char
Have a Hash-map/Dictionary for “first occurrence” and the “occurrence count” For each char in string when you add for firs time to “occurrence count” add the index to “first occurrence” and then pick the first based on values of both hash-maps. Store the value for each char in string as a object which has first occurrence index and no of occurrence Filter by no of occurrence and check the lowest first occurrence
This is how I approached it at first. I’d have a list of occurring characters and a list of first indices. When I find a second occurrence, I eliminate it from the list of first indices (and don’t write it there again). When the string is complete you’ve got your answer in the first slot of the first (non-null/missing) indices array.
You can also optimize complexity by using map pair(0) will contain the frequency and pair(1) will contain the index of the char. So looping through map for finding solution will not always be O(n)
You could also just remove the char from the original string as you loop through if it if it is repeated by looking at the map. Then at the end the first char is either the first non repeated char or the string is empty.
What if you loop through once - using a dict with the key as the letter and the value being the index. Then you return the character with the lowest index out of all non repeating chars at the end...
my first thought, was create an array size 26 (one for each possible character) and when you check each character in the string, increment the element for said character by 1. (so each time youd encounter 'a' then arr[0] += 1, for each character in string) then once done, loop through the array and find the first element == 1 and return that. if all elements are != 1 then you know that there are no non repeating characters. and would thus return '_'. id probably also create a constant string with all possible characters in order to simplify the conversion between tracking array and corresponding character. not the most efficient way, but its simple, easy to implement, and does the task. and can be done with 2 loops in said function.
I just started programming and I am really happy that this was the first interview question that I managed to get it done so I am going to post my code here and hope that one day in the future I will come back to this video and see it again. string = 'aaaaaaaaccccccccceeedf' lista = list(string) lista_copy = lista[:] first_non_repeated = None for element in lista: being_analysed = lista_copy.pop(0) if being_analysed in lista_copy: while being_analysed in lista_copy: lista_copy.remove(being_analysed) else: first_non_repeated = being_analysed break if first_non_repeated: print(first_non_repeated) else: print('There is no non repeated symbol')
That's python code, right? I tested it an it throws an error when there is no non-repeated character: "pop from empty list" Your for loop is in fact broken and needs to be replaced - because it goes through every element in lista, which is: a, a, a, a, a.... -> meaning it will run len(lista) times and causes the pop-error because if you don't reach the break, it will end up with an empty lista_copy while still within the loop because len(lista) is so long. I streamlined your code a little, by using a while-loop with an else (the while-else is executed at the end of the while-loop, however the break exits the loop and skips the while-else as well). string = 'aaaaaaaaccccccccyceeedydff' lista = list(string) while len(lista) > 0: being_analysed = lista.pop(0) if being_analysed in lista: while being_analysed in lista: lista.remove(being_analysed) else: print(being_analysed) break else: print('There is no non-repeated symbol')
@@Shuizid I didnt get this error but I did it again and endend the same way as your code(almost) string = 'aabbbced' lista = list(string) P = False index = 0 while lista: element = lista[index] if lista.count(element) > 1: while element in lista: lista.remove(element) pass elif lista.count(element) == 1: print(element) P = True break if not P: print('Tehre are no repeated elements')
my initial thinking is use a hashmap and populate it with all letters with 0 as its pair. Everytime we see that char, check if its in hashmap, if it is, then increment the int associated with it by 1 if its 0. If its 1, then that means we found a 2 instances of that char in the string and we remove that key value from the hashmap. We would also keep a stack or queue to keep track of which char was found first. Every time we discover a new char, we push onto the stack/queue. Then whenever we remove a char from the hashmap, we also remove it from queue/stack. The stack/queue only ever keeps one instance of the chars. Its purpose is purely to keep track of when we find a new char in that order. At the end of iterating through all char in the string, we return the First element in the stack/queue. If its empty, return the '_'. This would give time complexity of O(n) as we have a single for loop to iterate the string. A space complexity of O(52) since we only ever keep track of 26 characters in our hashmap and stack/queue at worst (string has all characters once).
I actually used a LinkedHashMap with my initial solution so I don't have to loop through String twice, but the raw array version takes less than half the time with longer strings. Also while writing test case for this, learned that in Java, String literal could be maximum of 2^16 characters in UTF-8 encoding. thanks for teaching me something new today :)
My initial thought was to create a hashmap (I guess, haven't gone through DSs yet :x), and as we loop through the String, we either add this letter and it's index to the map (if it hadn't occurred yet), or change the index to -1 (if it did). Then we just return the letter at smallest, but positive index (or '_' if all are negative) and voilá. This way we only have records for letters that occurs. Especially efficient for long-ass Strings of only 8 or so distinctive characters
I was thinking of iterating over the string and save the char in a list, then, if the next character is on the list, delete it. Then, at the end, return the first element of the list.
I tried this out before watching the video -- here's what I came up with: public static char firstNonRepeating(String input) { // At the end of the loop, output contains all possible candidates for non-repeating characters String output = ""; /* 26 is more than enough for our puny, English lowercase minds... * We keep track of which characters we've seen with a boolean array. * In the biz, this is called premature optimisation, and it's bad. * */ boolean[] disallowed = new boolean[26]; for (char c : input.toCharArray()) { /* You can actually do arithmetic with chars * Subtracting 'a' from the char just normalises * it to a value we can use to index the boolean array * */ if (disallowed[c - 'a']) { // There are more efficient ways to replace the now-repeated character, but this works too. output = output.replace("" + c, ""); continue; } output += c; disallowed[c - 'a'] = true; } return output.isBlank() ? '_' : output.charAt(0); } It's O(n) in theory but probably closer to O(n^2) in practise because of the replace call. You could make it more efficient by using a linked list of characters and keeping track of the characters' indices -- that'd probably get it down to O(n) even.
I create a time complexity of O(n+m) using a LinkedHashMap in Java, where n is the size of the input and m is (at its worst) the 26 letters in the alphabet. For the LinkedHashMap, the key is a char and the value is each time it appears in the string. First loop loops through each letter in the string and charing it, adding new keys each time it finds it or incrementing the existing key's value by 1. After this loop finish, the last loop will iterate thru the LinkedHashMap's keySet and because LHM's are special in that it maintains the order as each key is added. When it reaches the first key with the value of 1 simply return the key. If it loops through all (at its worst 26) possible keys without getting a value of 1, then return the "_".
For the second loop you could build an array during the first loop, to save the order of first time seen. Which will be a length of 26, so an O of N+26.
Similar idea if using JavaScript would be to use a Map object, instead of a literal one. Then you can iterate through properties, since it does by order of creation.
@@inordirectional "The Unique Characters rule rejects passwords that do not contain a minimum number of unique characters. For example, the password "aaaaaaaa" only contains one unique character (a), whereas "mypassword" contains nine unique characters (mypasword)."
He could use additional memory(also helps with additional character sets, m is at worst the set of the characters) and just use a linked list and add a character on everytime a new character is seen by checking the hashmap for number of occurrences. Then at the end of the first iteration of the array of characters, iterate through the linked list(which should just be the order of characters indvidually), then check for each character in hashmap. First one to have a value of one is it. That should be a complexity of O(n+m) e.g. itt 1: _ string: aabddddbc Hash: {a:1} linked list : (a)->() itt 2: _ string: aabddddbc Hash {a:2} linked list: (a) ->() itt 3: _ string: aabddddbc Hash {a:2, b:1} linked list: (a) ->(b)->() .......... last itt, itt n: _ string: aabddddbc Hash {a:2, b:2,c:1,c:4} linked list: (a) ->(b)->(d)->(c) Iterate through linked list checking hash for first ct of 1 of the character and stop. NOTE: PLEASE LET ME KNOW IF I MESSED UP SOMEWHERE
Instead of an integer array you can also use just one integer. Since an int has 4 bytes, we have 32 bits available. Given that the string only contains English characters we have enough space. Each bit in the int can be flipped "on" (1) and "off" (0) when we encounter a character (e.g., if we see an "a" we mark bit 0 to 1.. if we see an "a" again we mark it back to 0). In the end we scan through the string again and return the first character which has a 0 in the bit representation at the position of the character in the English alphabet.
He didn't capture the index, but he does still have access to the string. That last for() loop is looping over the characters in the original string and checking them against the count in his hashmap until it finds one that appears only once. It's funny though, the first method I tried, I actually did make that mistake and returned the character that appears once in the String which is alphabetically first
Even though the runtime is O(n) after two runs, we can do this in one run over the list and optimize the runtime over memory usage by using a DoubleLinkedList and two Sets. Just add the elements to the end of the List if they are not yet in the "seen" Set, remove if already found. Just return the head of the list.
@@shrikantwankhede8317 I don't know if I was clear when I meant "optimize". I didn't mean we would get to O(1) but we could spare one run over the array, essentially still being O(n), but with only one pass over the array. So it's just an optimization, not really so much improvement on the theoretical complexity.
Nice video! Just a tip, in this instance you don’t need a Dictionary (aka Hashmap) because we don’t care about counting how many times a character occurs; we only care about whether or not it occurs more than once. A set (C++) or HashSet (C#) is the data structure you’re looking for. Not sure what it’s called in Java.
Vishal Patel initialize an empty set. For each character, check if it’s in the set. If not, add it to the set and continue. If so, then we know that it occurs more than once.
I stumbled upon this video and thought "oh this question is simple" and quickly realized it's a bit more difficult than I expected. took me about 35-40min to get this done w O(n) complexity and O(1) space. Great video
@@VishalPatel_imvishal create a hash table with all letters as keys and ints as values. traverse the whole str and increment all the key-values in the table. Then go back through the same string again and search each letter of the string in the hash table. The first letter that comes back with the value of 1 is the first non-repeating thus O(1) space.
I literally thought hashmap initially. But what scared me from that idea was handling if that was the first non repeating character. It isn’t sorted so there isn’t a way to know just off that. And my mind kinda went blank from there
amogh kulkarni hmm okay. I like that. Does that require extra time though ? If you’re inserting the key/value pair, that sort at best , could be log n maybe? and that’s extra time on top of simply inserting in a normal hashmap in 0(1) . I personally like the idea of 1 pass to put in the map and then pass once more over the string and comparing that to the value at that key and if it’s the first value that’s 1, return that key. But I wanna look into your solution. I didn’t know it was a thing
@@tannerbarcelos6880 Here is what i did. Now, i dodnt know how much time it will take, you can calculate and share the findings here. String sample = "ababcd"; Map sampleMap = new LinkedHashMap(); for (int i = 0; i < sample.length(); i++) { char c = sample.charAt(i); if (!sampleMap.containsKey(c)) { sampleMap.put(c, 1); } else { sampleMap.put(c, sampleMap.get(c) + 1); } } System.out.println(sampleMap); for (Entry entry : sampleMap.entrySet()) { if (entry.getValue() == 1) { System.out.println(entry); break; } }
Hash map does not maintain order. So in this case when looping through the map, it’s not guaranteed that you get the first character that has 1 as the value.
First solution that came to my mind was to split the string on each character into an array. Then delete duplicates from it and return the first index or underscore if the array is empty. Not saying it's the best solution, just the first thing I thought of.
@@makagyngrimm3392 Wouldn't deleting all duplicates be O(N^2) though? For every letter you'd have to scan the rest of array for the same letter to delete.
Use 2 arrays of length 26. One for occurance count and other for first occurrence position. After populating these arrays just find the char with occurrence count 1 and minimum first occurrence. It'll give O(n+26) which will better then O(2n). I know both are equivalent to O(n) but for large n, it'll make much difference. I consider O(2n) = O(n)+O(n) and O(n+26) = O(n) + O(1)
I love your videos man. So helpful. Another solution that’s better than brute force but isn’t as good as the optimal is to sort characters O(nlogn) and compare the characters next to each other
@Harsh Mehta That could work if the mapping was ( old index : new index ). Then you iterate using the new indexes by retrieving them from the mapping by calling the old indexes from 0 to n. Then all you'd have to do is compare both adjacent elements. for(int oldIndex=0;oldIndex
I thought of something else. For each letter put you find it has a duplicate put it in an array and precheck each character if it exists in the array then proceed on. If all goes well it will return the requested character. But ik your way is way more effective since arrays take a lot of space in memory and the process will be slower cuz you'll have to precheck everything with an extra for loop. I need to be more comfortable with using boolean lol
I have combined his way and your way actually. Have an array of 26 counters (made them int8_t or char because you only need to distinguish between 0, 1 and >1, you don't need specific count when in >1 case) and a string of capacity 27 which is appended the first instances of each character I encounter (capacity 27 so I also have a NUL terminator). After the string is done I loop through the second array and use the first one to stop at the first character which has a count of 1 rather than >1. Then if this loop finishes I will return the '_'.
I think a better solution is instead of storing the count store the index you found the character at initialized as -1. When you see a character update the -1 to the index or if it's already not -1 remove it from the hash map. At the end just loop through the hash map looking for the lowest value that isn't -1. This is much closer to actual O(n) for along strings as the second loop you only need check max 26 keys. If you want to get even more efficient you can still do your method when the number of keys is greater than the length of the string.
I understood the question differently. I would think a non repeating character is not the same as a character that only occurs once. For example in abbac I would say a is the first non repeating character, even though there are 2 a, I mean it doesn't repeat, there is a b after the a. Most recruiters appreciate it if you ask questions to clarify the task.
It’s worth mentioning (but not coding) the O(nlog(n)) solution too. If we sort the array, then repeating characters are next to each other. Then we can use two adjacent looping pointers, curr: one that stores the current character it sees, next: for the character at i + 1, and a third variable for running tally. If the next character identified by the pointer is a different character and the tally == 1, return arr[curr]. If we reach the end of our array with the next pointer and it’s equal to arr[curr], return our “_”. This is constant space and is a legitimate tradeoff vs a constant time, linear space solution, though we usually prefer faster time over lower space. Writing the sort function for characters can be annoying too, taking up about 10 minutes. On a real interview, you want to mention all of this, then get to writing the code for the solution that you can reasonably implement in 30 minutes.
Bro, i have seen many videos for competitive programming and none of them explained the solutions or even the questions this way. Keep up the good work. Your videos really helped me a lot. 😊
A better solution could be O(n + 26) = O(n) [lower than your O(2n) = O(n)], by just having the same 26 size array indexed by the number of the letter as you explained, but instead of storing the count you could store the index where you first found the letter, if during the traverse you find that there is a repetition then set the index as -1. After finishing the traverse, just check the 26 size array and find the lowest index in there, if all of them are -1 then there the answer is "_"
HashMap is a wrong choice. Hash map doesn't guarantee the order of insertion. You need to use LinkedHashMap if you want to preserve the insertion order in java.So in your example at 8:50 , it may give you d or f, if you are using normal HashMap.
we’re not looping through the hashmap which i explain in the video we’re looping through the string once again and doing lookups to fine the first character that has a frequency of 1
Shery's right - HashMap doesn't guarantee the order of insertion (www.geeksforgeeks.org/differences-treemap-hashmap-linkedhashmap-java/). The Python OrderedDict guarantees the order of insertion (docs.python.org/3/library/collections.html). Here is basically the above implementation using OrderedDict - import collections from collections import OrderedDict def firstNonRepChar(inpStr): odS = OrderedDict() for c1 in inpStr: odS[c1] = odS.get(c1, 0) + 1 for c1 in odS.keys(): if odS[c1] == 1: return c1 return '_'
This one is obviously doable as O(n): Two 26-element arrays, one (count) initialized to 0, the other (first_seen) to MAX_INT, then loop through the input, starting at the back end! do { c = inp[--pos] - 'a'; count[c]++; first_seen[c] = pos; } while (pos); Afterwards we just do the constant-time scan of those two arrays looking for those with count==1 and first_seen as low as possible. For extra credit write a SIMD version (somewhat hard to make efficient). A GPGPU would actually be more straight-forward. With really large inputs we could do a multi-threaded version with a reduction step/merge of the partial results at the end, this should easily be able to saturate the memory bus.
Fact: The HashMap solution is considered O(n) space as number of inputs isn't fixed, while the frequency array[26] approach is O(1) space as range of input is predefined, what's funny is the HashMap might actually use less space than the frequency array, as the frequency array also has to allocate space for non occurring characters.
Second method of using 26 array elements will not work for input like “azavbb” (seen in this video at 1:00), as it will have 1 for both ‘z’ and ‘v’, when we scan array to check for first element with 1, we get ‘v’ but correct answer in that case is ‘z’ as it is the first non repeated letter when scanning from left to right.
Hi Aleks, you are likely to have a key more than once which violates the building components of hashmaps and won 't be efficient for what you are looking for
@@brianotienotruimp you're not going to have a key more than once as you'll check to see if the key already exists.. if it does simply add to the increment for that letter.
you dont need to even use a hashmap. you can use the ascii code of a char as a direct index in an array: intarray[(int)string.charat(y)] gives each character a unique position in the array. The int values of chars a-z is 97 to 122, and you can cast a char directly to an int. public char firstnonrepeating(string searching){ // index in this array will be the ascii code of each char, value the count int[] found = new int[122]; // index in this array will be the ascii code of each char, value the last index int[] lastpos = new int[122]; for(int j = 0; j < searching.length(); j++){ found[(int) searching.charAt(j)]++; //count each character lastpos[(int) searching.charAt(j)] = j; //store the last index of this char } int position = searching.length();//keep track of the char found = '_'; //the array will contain all counts, find the one with the smallest position for (int i = 97; i
You can actually do it in a single pass if you store the position of the character. Also: you don't need to store the count, just the flag whether it occurs more than once.
Just joined Bachelor's in CS. At first thought I know that it can be done in two ways , •First by nested loop , by checking every index, but I know that it will take more time. (Once I got similar problem in Programming contest. I did it by looping, but I got TLE. So later I got to know about Hash Map) •Second we can do it by using hash map.
I guess it doesn't specify whether or not they have to be "directly repeating" or just "repeating" within the string. I agree though that "Unique" would be a better term to have used.
Without looking at the video (so his solution may be better than mine). Put the characters into a LinkedHashMap where the key is the character and the value is the total occurrences of the character in the string. Then, remove any element from the map with a value higher than 1. Then, return the first of the remaining entries on the LinkedHashMap. (Note: It is important to use a LinkedHashMap since it keeps the order in which the elements were inserted)
I tried this myself before watching solution. Took me like two hours to create this 60 rows long monster that somehow actually worked, but then I played the rest of the video and couldn't believe how easily it can be solved 😂
That last solution, where you compare indexOf() to lastIndexOf(), is not O(n). Since both indexOf() and lastIndexOf() both need to loop through the string, and you're calling them on each iteration of the outer loop, you're back to O(n^2), so while the code looks much cleaner and I would prefer it in a situation where string lengths would be guaranteed to be small, it is worth pointing out that it is not an optimal solution in terms of time complexity, and probably wouldn't pass an Amazon interview.
Proposed solution= create empty seenArray for each letter, determine if it is already in seenArray, if it doesn't already exist, push letter onto [end of] seenArray, if if does exist already, remove existing letter from seenArray (don't add current letter to seenArray) proceed to next letter for sample.length-1 times once end of sample is reached, return seenArray[0] Note: I just discovered your channel and I like the content so far. Great job! My software development experience is limited to a few projects and the first few sections of freecodecamp. I haven't covered data structures yet but I've seen a few videos touching on the topic. I still immediately think of stacking with arrays. I could be wrong here but this method seems worth mentioning as I think it should be O(n) with limited space. I'd love it if someone schooled me if I'm misunderstood here. Looking forward to the rest of your content, Nick! keep it coming.
Loop through the string with with a for loop --> use the method "lastindexof" with your current character. If the index that the method returns is equal with your current index than the character doesnt repeat. Thats the first solution that came into my mind. And you only have to loop through it once.
great vid, there 's an option to use insertion ordered data structure (like dict in python or vector in cpp) and increment the keys after their value passes 1-->O(n)
This was similar to my first thought. Define a queue containing characters you've only found once, and as you find a duplicate character, take it out and move it to a set containing characters you've found more than once. I believe that solution is O(n) as well, and it's nice that we don't have to worry about counting. I think I still like the int array solution the most, though.
unless they specified what job this is for a coding interview can range from all sorts of coding related jobs, you definitely don't need much more than this if you're just going to be doing some assistance or something
This was still not an optimal solution. 2 integers could be used to store all of the needed information in their bits. Also, providing information about the actual complexity of the HashMap, which is constant, but not 1, would show that you are a more advanced developer.
Hey, buddy. In your first "brute force" example you don't have to start with j=0. The situation here is similar to bubble sort, where second loop doesn't need to look for previous elements, because they were handled in previous loops, so make it j=i++
Instead of looping through the entire string a second time to find the first unique char, take the index of the first 1 in the char counts array, add the ascii code for 'a' and that's your character. Would be faster as you only have to loop through 26 chars at worst.
Why the second loop over the string? You could record the index in the hashmap instead of the times it occurs, and if it occurs more than once, replace the index with -1. Then, loop through the keys of the hasmap and record the lowest index.
I wanted to ask bc my friend told me about it when interviewing, btw this did help me understand what companies want from someone, anyway my friend told me that if they give u a question u already seen and solved that u should tell them, is that a good idea or no??
I say it depends how well-rehearsed and familiar you are with the question. If you literally know the exact steps, I would be honest with them, but also be clear with the boundary conditions of your solution. Then maybe, they would ask further constraints to the same problem (any good interviewer should do this) or ask a different problem. The main goal of these interviews is to see how well you can communicate your thought processes and divide a problem into smaller/logical chunks under a time constraint. I think the big mistake a lot of people make is going straight to coding without giving a good big picture step through of the problem and how it can be solved. Implementations can then vary.
This solution seems more like it should be "first unique character" Also in the case of the the array[26] solution, wouldn't it actually iterate alphabetically meaning you would get the "first unique character alphabetically". If all inputs are alphabetically sorted then this isn't a problem but It doesn't specify that anywhere. I think it would be more safe with using the hashmap
No, you dont iterate through the array, the same as you dont iterate through the hashmap. You iterate over the input string only. And with both, hashmap and array[26] you have constant time of getting the value that represents the number of occurrences. In hashmap, you calculate the hashcode, and in the array, you calculate the index with the letters like b - a = 1 for b, d - a = 3 for d etc. Same thing.
for example : String s = "aaaabccdeeff"; return s.toCharArray().stream.filter(c -> s.indexOf(c) == s.lastIndexOf(c)).getFirst().get(); or even String s = "aaaabccdeeff"; for (char c : s.toCharArray()) if (s.indexOf(c) == s.lastIndexOf(c)) return c; return '\0';
Java is horrible for reading (or working) unless you really have to work with Java as the company requires, otherwise Python is way better to work and read.
"non-repeating" here seems fairly misrepresentative of what you're actually doing given the rules explained. At best, it's super vague. I would prefer the word "unique", myself. I could MAYBE consider "non-repeated"; but "repeating" implies that the letter is the same in the order given. Not really YOUR problem, I guess; and as long as the rules are there it doesn't matter too much. Just seemed weird.
I agree that "unique" would be less unambiguous to use. However, "non-repeating" is not necessarily incorrect. I think they consider a character being a repetition of an earlier character to count as "repeating".
Agreed. I initially interpreted the scenario by thinking repeating was only if it was sequentially repeated, not that repeating meant no duplication of a character in the entirety of the string. (Past tense of the verb repeated vs active verbiage use of repeating is interpreted differently in my mind). I.e. aabcd would return a, but abcabd should also return a as a was not directly followed by another a. So I think first unique character, or first character that has a count = 1, or something along those lines would be better in giving a firmer grasp of the scenario presented.
What about this solution (only loops once): string = list('abacabad') not_repeating = [] visited = [] for i in string: if i not in visited: not_repeating.append(i) visited.append(i) else: if i in not_repeating: not_repeating.remove(i) if not not_repeating: # if not_repeating is empty print('_') else: print(not_repeating[0]) >>> c
This solution is good if a lot of the characters in the string are not repeated consecutively, or there is not a unique character within the string. Note: This solution is actually O(N^2) as it loops through a list again, and we have to store two more lists than needed to solve this problem.
In the map, first time add the Index value of a character as a value to key (character), and later instead of adding a count of occurrence, just make the value of a key (character) as -1 if it's repeated. Now iterate over unique keys from the map and not input array (so it will be less in number as compared to original string ) and check for lower index character .. here you got the solution.
for non-repeating characters, my idea to optimize stuff is just scan the string when finds a letter, after scanning it turns all duplicates into let's say zeroes, that are simply ignored, so if you have aaabccc..., it just scans the entire string once for a and once for c, however i think it would go below O(n*log(n))
I dont know if only Python has count method? In python i would do like this: for loop (for char in string) then if string.count(char) == 1: return char, else string.replace(char,'')
You can do it in python with storing occurences in a tuple then turn the tuple into an array(that only takes a value once ) and make it print the first corresponding character from the string that has occurence equal to 1
Why not create a second array that populates with the letter found for each new index position and then loop through the first array (the one with the number of hits) the second time instead of the entire string? You'd only have a maximum of 26 items to loop through in the array as opposed to the possible 100,000 duplicate characters in the original string. Once you find the first index with a 1, you check the second array for the letter that was originally found for that index position.
I once had an interview with this company called ViaSat. I literally only studied 1 coding question the night before and it was this one. Out of pure coincidence, the whiteboard question they asked me to do was this one (the only question I had studied.)
God loves you
@@blasm1713 shut up
@@jinxy7869 god loves you too
@@blasm1713 LMAOOOO
Did you get an offer?
Your channel helped me a lot to brush problem by watching them over and over, finally got a offer from Amazon thanks a lot
Great
Which position?
@@chandud4255 lmao
@@knight_23 SDE 1
@@fertwvnbxcbwrtrecvbvcx joke on you, kid
The complexity of the last solution (with the builtin indexOf methods) is O(n^2). Those methods traverse the array to find those indexes.
yeah exactly, doesn't seem like a good solution. I would use some kind of structure to keep track of the first encountered position of each character as well as the total count, and you can use that after parsing the string to quickly find the first one, that's O(n)
@@Alistair You can also loop over the alphabet instead of whole string, with complexity 26N = O(n).
the complexity of the solution as presented in code is really O(n^2) but the idea can be coded in O(26*n) (i.e. O(n)) if the outer for loops through the set of 26 possible symbols rather than through the input and records the minimum symbol-indexOf pair. Actually it is a nice representation of the solution with functional/logical programming properties, a version of looking for minimum element.
Of course the problem can be solved in a single pass, so if really striving for time efficiency, even two passes are two much, more so 26.
@@popularmisconception1 you mean to take a pair of last and first index for each letter?
Instructions not clear I got hired as the CEO
So you won by failing?
Nice
BigHead is that you!?
nah, sorry not funny
Task failed successfully
Another way to think of using an array indexed by each letter’s place in the alphabet is that this is still a hash map. You are deriving the location in memory of each piece of data by using a key’s hash - it’s just that you have a closed set of keys, so you can have an incredibly simple hashing function.
Love the quality of this vid, a chop above your standard stuff nick thanks for putting in the effort!
What about LinkedHashMap? They are sorted the way in which you are entering the key-value pair, so we can go with a for-loop in the end just to find the first key that has value 1.
I came here to see if anyone mentioned this. If you're going to use a HashMap anyway then you might as well use a LinkedHashMap and then iterate through that to find the first with a count of 1.
@@mammlouk Yeah exactly, in general it's better to just use LinkedHashMap over HashMap, just because in the end you know where each element is. And this example here is just perfect for LinkedHasMap.
That's the solution I came up with. I used a LinkedHashMap to keep track of entries and a boolean array to mark bad characters. When coupled with streams, you can filter as you're going through the character array and remove items from the map. Then at the end it's just testing if the map is empty or picking off the first key.
THANK YOU!! I was yelling this at the screen.
How would you explain linkedHashMap to the non Java interviewer?
There is one problem with your solutions. For the 26 long array solution, what happens if you give it the input “fall”? ‘a’ will be 1 and ‘f’ to 1, looping through afterwards gives us ‘a’ as the first non repeating character, but what we actually wanted was ‘f’.
For the first hash-map solution, there are some different implementations which can also affect the order of the keys, which in turn makes the looping through to get the one with count 1 unpredictable and may yield false results.
Great video bro... Just a doubt isn't the last solution O(n^2) because maybe .indexOf() and .lastIndexOf() has O(n) complexity internally and we are iterating through the array therefore O(n^2) ???
That's what I thought. I'm very wary of using builtin commands because often times they have their own complexities
Depends on implementation but in most of the cases yes.
@@JohnTrustworthy You cannot perform better than O(n)
@@quyenv.nguyen6130 Hash algorithms?
John Trustworthy those would require hash map, not array. And then there wouldn't firstOf make any sense. The best you can do is O(n).
The indexOf and lastIndexOf implementation, the cost is N^2, because the implementation of this function it's a loop so it will be a loop inside a loop -> n^2
Really depends on the language. Since the array doesn't change after the first lookup it will act as a dictionary and spit out indexes without going through the array.
Even though time complexity doesn't change, you can still lower the constant by storing the position of the first encounter of the letter, it would change from O(2n) to O(n+26) which on large strings is faster
The array could store 0 for not encountered, index (starting at 1) if encountered once, and then -1 if encountered more than once. Then just scan the array for the lowest value and remember that index. The only states that need to be remembered are not seen, seen once, or seen more than once. Only seen once needs the index. Thus the other two states can be single integer values different from a valid index.
@@gblargg that would save on memory, but not on speed. adding 26*sizeof(int) to a solution is no big deal, but i guess you're right
@@gblargg When storing only ~104B+len(sequence)B in memory it's extremely unlikely storage is a larger concern than speed.
@@starskiiguy1489 My point was about representation, and thinking about when the location is even required. There is some practical value to not having multiple structures you have to manage separately, and having less redundant state. I think it's useful to be able to explore various ways of implementing things, looking at each from multiple angles.
i would use a linked list, an array of 26, and a counter for duplicated letters.
every time the count for a letter changes from 0 to 1, push the letter onto the end of the linked list, change the array[char] from 0 to 1.
Every time the count for a letter changes from 1 to 2, scan the linked list for the letter and remove it, change the array[char] from 1 to 2. and increment the counter.
Do not do anything for any count changes.
if the counter reaches 26 before the end of the input string, return "_" immediately. otherwise, return the first element of the linked list when you reach the end of the string.
The time complexity is O(n) for scanning input string, plus O(1) for pushing to linked list, plus O(1) for scanning linked list for removal because maximum is 26, plus O(1) for array access.
Time complexity is O(n + c) = O(n)where c < n for n > 26.
whereas if you do the hash table and scan you will have O(2n) = O(n), because the unique letter might be at the end so you will have to scan the entire string twice
Since we are looking for the first character instance only, we can use a regular variable to store that character. It reduces the memory used.
I agree, this way you only really do 1 loop around the string. Another way is to use split and count the length of the resulting arrays hence if the length is 2 then you have your unique character.
@@fidelischarles4545 But the creator of this video kept counting after 2. If the string is long or contains a lot of the same character, we waste some time. Skipping a character would be rewarding. Is there an actual reason to do so?
@@LenaUA-cam Well, to skip the character you first have to check if it's already marked. In a complex data structure, just to find one number can take a whole algorithm.
At the best it is going to be O(1) time which is the same if not skipping it. In case we were finding all the unique numbers I guess a splitting array makes sense.
@@siddhantjain2402 well said
How does that handle abbbbcddddddeeeeeefffa ? I would use a 2nd map (array or hash) to keep track of position of characters with a count of 1 (remove when it exceeds). At end loop through that 2nd map which is O of the cardinality of the char set (which is constant)
A simple optimisation for the double for loop: initiate j as i+1, since there’s no point repeating earlier characters that have already been tested and are known to be repeating
This is kinda late but if the string was "aaabcccda" the last 'a' would appear to be non repeating even though it does repeat.
With "aaab" that would return 'a' since the last a would be counted as nonrepeating.
from the thumbnail i thought this was a trick question as they asked you which character is the first non repeating character and the first a is because there were no a's before that a
even if the question was first non sequentially repeating, the first a is repeating since the next character is also an a.
you can have an ordinal value starting at 1. instead of storing the count in the hash, you store the ordinal the first time (and increase the ordinal by one), if there was an ordinal already, set it to -1. Then after you finish the array once, you just search the hash for the item with the minimum positive value. That's your 1st non repeated. Instead of O(2n) you have O(n+26) = O(n) which is better specially for big arrays.
When I first attempted this I differentiated grammatically between the meanings of 'repeating' and 'repeated'. 'Repeating' I inferred as coming up next to again and again etc i.e. n instances of the same character adjacent to each other, whereas 'repeated' was what I inferred that the question is actually asking for i.e. is repeated elsewhere in the string. Semantics maybe, but don't get caught out folks like I did :)
why its always important to ask clarifying questions to an interviewer if you're not sure.
You could also start at the back and keep a list of all chatacters found. Then every time you find a character you haven't yet seen, you store that as your candidate. The last one standing is the one.
Edit:
I suppose that you would have to search the string as much as you search the hash table. If not one time less since you don't have to do it at the end.
it would be ~O(26n) instead of ~O(2N) since you go through a 26 char array N times. it would actually be faster to dummily increment each value in some sort of ordered hashmap and search after for count==1.
@@satibel For example dictionaries in Python
Here’s my solution, i believe it only takes a single for loop (O(n)):
- Start at the end of the string, iterate backward
- Keep a hash map as in the video with the number of occurrences
- Also keep a single character which represents the last encountered letter
- In the loop:
1. If the character has been seen already (hash map not zero) add 1 and continue
2. Of the character has NOT been seen already (hash map is zero) add 1, update the “last seen” character, and continue
- This way, we skip all the repeated characters once they are logged
- Once we get to the end of the loop, if the count of the “last seen” character is 1, then return that character (I.e. it was unique and closest to the start) otherwise return underscore
Amazon pls hire me for all your weird string filtering needs
That is the correct answer, although it wouldn't matter if you went forwards or backwards. You could also hash more information about the different locations, number of iterations when to break. and so on.
This is an incorrect solution. It would fail, for example, on case “aaabbaac”, returning b instead of c. The best case scenario is O(2n) no matter what, and I’m too tired to write out why right now. Ping me later to hear an explanation.
@@jajefan123456789 too long i didnt read his solution fully. But I feel this was his idea. It will return c because it was the last character with count = 1
pseudocode
dic = {}
lastCharWithCountOfOne = " "
for(end, beginning):
dic[character] += 1
if dic[character] == 1:
lastCharWithCountOfOne = character
if lastCharWithCountOfOne != " " :
return lastCharWithCountOfOne
else:
return "_"
@@anujramaswamy6809 would this works? You sure?
This doesn't work. It cannot keep track of the correct last seen unique character in a single variable.
Just take the Wendell Wu example: "aaabbaac". At first the variable is c. Then it will instantly change to a, because it is the first occurence of that letter. It doesnt know that there will be more a's. So already we have lost the correct letter, which was c. Then it will update to b, and at the end it wont even return that, because it wasnt unique, it will return underscore, which is wrong.
You don't actually need a hashmap. Just create a bit vector associated with the character's ascii value. You don't care how many times it happens, just update a single bit. It will be almost constant time/space since you only need 56 bits to represent the entire a-zA-Z alphabet.
I thought exactly the same, but the only thing you have solved is which letters of the alphabet have a representation in the string and which of them appear more than once, hence lacking the knowledge of which is the first letter that appears only once.
To solve this, you can XOR both vectors and loop through the string again, when you access such XOR'd vector and find a 1/True, you found the first non-repeating letter. It is O(2*N) which simplifies into O(N). You can check if the XOR gave 0 before looping to know if there were no letters satisfying the criteria.
It is worse than other implementations but it is the least memory-hungry one. Only 2 long int to save all that information (plus whatever pointer/index you use to loop).
@@VilasNil good point.
I find myself tempted to use recursion here:
// Find the first non-repeating character in a string
// Returns null for empty strings and strings with no unique chars
function findFirstNonRepeatingChar(str) {
// Get the first character of the string
let char = str.charAt(0)
if(!char) return null;
// Replace all instances of that character
let repl = str.split(char).join('')
// Recurse if you replaced more than one character
if(str.length - repl.length > 1) {
return findFirstNonRepeatingChar(repl)
} else return char
}
Thankfully the stack depth won't be fucked but can you tell me O(what) this is? (time and memory) You need to have this skill at the interview (I stopped myself from giving you the answer).
@@paulstelian97 That's a good point... The worst case would be all duplicate characters, so I guess it would be O(n * k), where n is the length of the string and k is the number of unique characters (max 26). There are only 26 letters in the question, so it's a maximum stack depth of 26, and the string shrinks by at least 2 until an answer is found...
That said, you make a good point. Recursion makes the code easier, but it takes way more memory/stack space than a simple loop.
@@Krechevskoy Sure. Since k is limited by 26 you may as well replace it by 26 (big-O shows the worst case indeed) which disappears as O(c * n) = O(n). So it is linear time, and I'm not sure what to understand of what you said from the memory point of view (the correct answer is also linear for the same reason)
@@paulstelian97 Yes, the memory is also linear, but it is also worse than a simple loop because of the recursion. Each stack frame needs to hold a (shorter) copy of the string, which is the typical downfall of recursive functions.
@@Krechevskoy The best algorithm has constant space (input is not considered if treated as read only).
Another more mathematical solution could be assigning each letter a prime number and using a for loop multiplying each prime number associated to the corresponding character, after that with other loop you start from left to right checking the reminder of dividing that result by the corresponding prime squared (with the operator %) if the answer is different than cero you return that character.
Sorry for bad English, please ask if you have any doubts.
Yea, but as far as I understand your solution you would multiply even 100000 times which would cause an integer to flip.
@@blazejeczek8710You only have to multiply once per character, but you are right, that could be a problem with really long character strings.
@@blazejeczek8710 for example, with the string abbcdda you get 2*3*3*5*7*7*2=8820 which can be divided by 2^2, 3^2, 7^2, the only prime squared in the list that cannot divide that is 25=5^2, so the result should be c.
@@sabazillo yea that is a clever solution in mathematical sense and it reminds me of a concept called hashing that can be used in other string/text problems (don't know if you are familiar with it):
Basically you do what you've talked about - choose a prime number for each character and multiply it and you add an additional step which is moduling each time by a choosen number, preferably a big prime like 10^9+7 (you don't ever overflow).
This way you can easily check whether 2 strings are composed of the same number of the same characters.
Example: you know that "aabbc" is the same as "abcab" because it has the same hash value.
But in this problem I think other solutions might be better due to the overflow issue.
Make one pass through the string and calling split with each char (str.split(substr(i,1))). If the resulting length = 2 then the char is unique.
A bit late, but split is O(n) so it would be O(n^2)
@@geekyvors2837 Correct
this video is more “phone user” friendly than the previous ones. Love it!
yikan wang get a computer broke ass
Wave TV I have a very good computer, still prefer mobile most of the time because if I’m on my computer I’m usually playing a game
Jack haters gonna hate. My laptop is above 1k. I brought UA-cam premium to watch this channel. I guess he’s gonna call me poor still. Just ignore him.I rather think he’s pathetic and feel a little sorry for him born in a bad family.I lift five times a week and keep myself lean all the time. If he hustles like we do he doesn’t got time to hate.I’ve reported him.
For some reason I code on my phone and not in pc most of time
indexOf is O(n) in all arrays implementation in languages I know. So the last solution, despite being elegant, is O(n^2).
Exactly my point. Hence hash maps/array of alphabets counts could be better than indexOf!
The third method using built in functions is dangerous, especially in an interview. It assumes that the built in function isnt bigger than polynomial. Your code code be constant time and the functions could be exponential. Whether it is or isnt, really isnt the problem, but before you opt to use it, be prepared to explain what its doing. Last but not least, a function call creates overhead, and doing a function call on each element will slow you down as the set grows. If you're trying shave off cycles, it's definitely a poor approach to call two function calls.
I like the last one. My solution was to take each letter in sequence, and then compare the string length, to the string length with that letter removed. If the result is 1 then you have the first non repeating letter, if not, use the string that has that letter stripped as the new input, and repeat until you get 1 as the difference in string lengths.
Nice
The last one in video doesn't work for the case there is no single occurance character, it'll print the last instance of any repeating character.
Your solution works tho
@@HeyItsSahilSoni How does it not work? .indexOf always returns the first index of the item and .lastIndexOf always returns the last index of the item. If they are not equal the function returns "-". It will not return the last instance of a repeating character.
So iterate over a string 26 times? You would fail my interview
i'm not sure but i think that there is a way simpler thing to do. convert the string to byte array then a for loop and at each iteration get the character in the array and verify if the character before and after is the same if not it's the first non repeating char
Have a Hash-map/Dictionary for “first occurrence” and the “occurrence count”
For each char in string when you add for firs time to “occurrence count” add the index to “first occurrence” and then pick the first based on values of both hash-maps.
Store the value for each char in string as a object which has first occurrence index and no of occurrence
Filter by no of occurrence and check the lowest first occurrence
This is how I approached it at first. I’d have a list of occurring characters and a list of first indices. When I find a second occurrence, I eliminate it from the list of first indices (and don’t write it there again). When the string is complete you’ve got your answer in the first slot of the first (non-null/missing) indices array.
You can also optimize complexity by using map pair(0) will contain the frequency and pair(1) will contain the index of the char.
So looping through map for finding solution will not always be O(n)
You could also just remove the char from the original string as you loop through if it if it is repeated by looking at the map. Then at the end the first char is either the first non repeated char or the string is empty.
What if you loop through once - using a dict with the key as the letter and the value being the index. Then you return the character with the lowest index out of all non repeating chars at the end...
my first thought, was create an array size 26 (one for each possible character) and when you check each character in the string, increment the element for said character by 1. (so each time youd encounter 'a' then arr[0] += 1, for each character in string) then once done, loop through the array and find the first element == 1 and return that. if all elements are != 1 then you know that there are no non repeating characters. and would thus return '_'. id probably also create a constant string with all possible characters in order to simplify the conversion between tracking array and corresponding character.
not the most efficient way, but its simple, easy to implement, and does the task. and can be done with 2 loops in said function.
I just started programming and I am really happy that this was the first interview question that I managed to get it done so I am going to post my code here and hope that one day in the future I will come back to this video and see it again.
string = 'aaaaaaaaccccccccceeedf'
lista = list(string)
lista_copy = lista[:]
first_non_repeated = None
for element in lista:
being_analysed = lista_copy.pop(0)
if being_analysed in lista_copy:
while being_analysed in lista_copy:
lista_copy.remove(being_analysed)
else:
first_non_repeated = being_analysed
break
if first_non_repeated:
print(first_non_repeated)
else:
print('There is no non repeated symbol')
That's python code, right?
I tested it an it throws an error when there is no non-repeated character: "pop from empty list"
Your for loop is in fact broken and needs to be replaced - because it goes through every element in lista, which is: a, a, a, a, a.... -> meaning it will run len(lista) times and causes the pop-error because if you don't reach the break, it will end up with an empty lista_copy while still within the loop because len(lista) is so long.
I streamlined your code a little, by using a while-loop with an else (the while-else is executed at the end of the while-loop, however the break exits the loop and skips the while-else as well).
string = 'aaaaaaaaccccccccyceeedydff'
lista = list(string)
while len(lista) > 0:
being_analysed = lista.pop(0)
if being_analysed in lista:
while being_analysed in lista:
lista.remove(being_analysed)
else:
print(being_analysed)
break
else:
print('There is no non-repeated symbol')
@@Shuizid I didnt get this error but I did it again and endend the same way as your code(almost)
string = 'aabbbced'
lista = list(string)
P = False
index = 0
while lista:
element = lista[index]
if lista.count(element) > 1:
while element in lista:
lista.remove(element)
pass
elif lista.count(element) == 1:
print(element)
P = True
break
if not P:
print('Tehre are no repeated elements')
my initial thinking is use a hashmap and populate it with all letters with 0 as its pair. Everytime we see that char, check if its in hashmap, if it is, then increment the int associated with it by 1 if its 0. If its 1, then that means we found a 2 instances of that char in the string and we remove that key value from the hashmap. We would also keep a stack or queue to keep track of which char was found first. Every time we discover a new char, we push onto the stack/queue. Then whenever we remove a char from the hashmap, we also remove it from queue/stack. The stack/queue only ever keeps one instance of the chars. Its purpose is purely to keep track of when we find a new char in that order. At the end of iterating through all char in the string, we return the First element in the stack/queue. If its empty, return the '_'. This would give time complexity of O(n) as we have a single for loop to iterate the string. A space complexity of O(52) since we only ever keep track of 26 characters in our hashmap and stack/queue at worst (string has all characters once).
I actually used a LinkedHashMap with my initial solution so I don't have to loop through String twice, but the raw array version takes less than half the time with longer strings.
Also while writing test case for this, learned that in Java, String literal could be maximum of 2^16 characters in UTF-8 encoding. thanks for teaching me something new today :)
You still have to iterate through the entry set of the map however which shares the length of the string, so this solution would still be O(2n)
Entry set is the string anyway so not sure would be worth.
My initial thought was to create a hashmap (I guess, haven't gone through DSs yet :x), and as we loop through the String, we either add this letter and it's index to the map (if it hadn't occurred yet), or change the index to -1 (if it did). Then we just return the letter at smallest, but positive index (or '_' if all are negative) and voilá. This way we only have records for letters that occurs. Especially efficient for long-ass Strings of only 8 or so distinctive characters
LinkedHashMap can keep the order !
Thanks
I was thinking of iterating over the string and save the char in a list, then, if the next character is on the list, delete it. Then, at the end, return the first element of the list.
I tried this out before watching the video -- here's what I came up with:
public static char firstNonRepeating(String input) {
// At the end of the loop, output contains all possible candidates for non-repeating characters
String output = "";
/* 26 is more than enough for our puny, English lowercase minds...
* We keep track of which characters we've seen with a boolean array.
* In the biz, this is called premature optimisation, and it's bad.
* */
boolean[] disallowed = new boolean[26];
for (char c : input.toCharArray()) {
/* You can actually do arithmetic with chars
* Subtracting 'a' from the char just normalises
* it to a value we can use to index the boolean array
* */
if (disallowed[c - 'a']) {
// There are more efficient ways to replace the now-repeated character, but this works too.
output = output.replace("" + c, "");
continue;
}
output += c;
disallowed[c - 'a'] = true;
}
return output.isBlank() ? '_' : output.charAt(0);
}
It's O(n) in theory but probably closer to O(n^2) in practise because of the replace call. You could make it more efficient by using a linked list of characters and keeping track of the characters' indices -- that'd probably get it down to O(n) even.
I create a time complexity of O(n+m) using a LinkedHashMap in Java, where n is the size of the input and m is (at its worst) the 26 letters in the alphabet. For the LinkedHashMap, the key is a char and the value is each time it appears in the string. First loop loops through each letter in the string and charing it, adding new keys each time it finds it or incrementing the existing key's value by 1. After this loop finish, the last loop will iterate thru the LinkedHashMap's keySet and because LHM's are special in that it maintains the order as each key is added. When it reaches the first key with the value of 1 simply return the key. If it loops through all (at its worst 26) possible keys without getting a value of 1, then return the "_".
youtube has been recommending me a lot of coding videos lately and I love it
IKR
For the second loop you could build an array during the first loop, to save the order of first time seen. Which will be a length of 26, so an O of N+26.
Similar idea if using JavaScript would be to use a Map object, instead of a literal one. Then you can iterate through properties, since it does by order of creation.
The naming is a bit fail,i'd suggest the function be named firstUniqueCharacter
Exactly my thought. The name suggests "aabaabbb" would return b, but in this solution it wouldn't.
Yeah, I agree with this.
Except there's already such a thing as a "unique character" such as $, &, #, @, etc. It's supposed to be as clear as possible.
@@e_tas_ Never heard anyone refer to non-alphanumeric characters as 'unique characters' though. Nonrepeating is clearly ambiguous, unique is less so.
@@inordirectional "The Unique Characters rule rejects passwords that do not contain a minimum number of unique characters. For example, the password "aaaaaaaa" only contains one unique character (a), whereas "mypassword" contains nine unique characters (mypasword)."
He could use additional memory(also helps with additional character sets, m is at worst the set of the characters) and just use a linked list and add a character on everytime a new character is seen by checking the hashmap for number of occurrences. Then at the end of the first iteration of the array of characters, iterate through the linked list(which should just be the order of characters indvidually), then check for each character in hashmap. First one to have a value of one is it. That should be a complexity of O(n+m) e.g.
itt 1:
_
string: aabddddbc
Hash: {a:1}
linked list : (a)->()
itt 2:
_
string: aabddddbc
Hash {a:2}
linked list: (a) ->()
itt 3:
_
string: aabddddbc
Hash {a:2, b:1}
linked list: (a) ->(b)->()
..........
last itt, itt n:
_
string: aabddddbc
Hash {a:2, b:2,c:1,c:4}
linked list: (a) ->(b)->(d)->(c)
Iterate through linked list checking hash for first ct of 1 of the character and stop.
NOTE: PLEASE LET ME KNOW IF I MESSED UP SOMEWHERE
Awesome, the way you explain makes programming even more interesting🔥
Instead of an integer array you can also use just one integer. Since an int has 4 bytes, we have 32 bits available. Given that the string only contains English characters we have enough space. Each bit in the int can be flipped "on" (1) and "off" (0) when we encounter a character (e.g., if we see an "a" we mark bit 0 to 1.. if we see an "a" again we mark it back to 0). In the end we scan through the string again and return the first character which has a 0 in the bit representation at the position of the character in the English alphabet.
You needed to capture the index to find the first non-repeating character. Your answer assumes the string is in alphabetical order.
He didn't capture the index, but he does still have access to the string. That last for() loop is looping over the characters in the original string and checking them against the count in his hashmap until it finds one that appears only once. It's funny though, the first method I tried, I actually did make that mistake and returned the character that appears once in the String which is alphabetically first
Even though the runtime is O(n) after two runs, we can do this in one run over the list and optimize the runtime over memory usage by using a DoubleLinkedList and two Sets.
Just add the elements to the end of the List if they are not yet in the "seen" Set, remove if already found. Just return the head of the list.
what about the time required to traverse the list...i am bit confused...can u explain the time complexities involved in it
@@shrikantwankhede8317 I don't know if I was clear when I meant "optimize". I didn't mean we would get to O(1) but we could spare one run over the array, essentially still being O(n), but with only one pass over the array. So it's just an optimization, not really so much improvement on the theoretical complexity.
@@alexluz321 okay....got it , thanks for replying
How I wish I get these problems during interview. I somehow always get maze, graphs problems :(
Nice video!
Just a tip, in this instance you don’t need a Dictionary (aka Hashmap) because we don’t care about counting how many times a character occurs; we only care about whether or not it occurs more than once.
A set (C++) or HashSet (C#) is the data structure you’re looking for. Not sure what it’s called in Java.
And how do you do that with HashSet? How do you know if the number is repeated or not repeated?
Vishal Patel initialize an empty set. For each character, check if it’s in the set. If not, add it to the set and continue. If so, then we know that it occurs more than once.
This is your daily dose of Recommendation
.
I stumbled upon this video and thought "oh this question is simple" and quickly realized it's a bit more difficult than I expected. took me about 35-40min to get this done w O(n) complexity and O(1) space. Great video
How did you able to do in O(1) space?
@@VishalPatel_imvishal create a hash table with all letters as keys and ints as values. traverse the whole str and increment all the key-values in the table. Then go back through the same string again and search each letter of the string in the hash table. The first letter that comes back with the value of 1 is the first non-repeating thus O(1) space.
I literally thought hashmap initially. But what scared me from that idea was handling if that was the first non repeating character. It isn’t sorted so there isn’t a way to know just off that. And my mind kinda went blank from there
Tanner Barcelos same here
you can use linkedhashmap it will sort the keys in added order.
amogh kulkarni hmm okay. I like that. Does that require extra time though ? If you’re inserting the key/value pair, that sort at best , could be log n maybe? and that’s extra time on top of simply inserting in a normal hashmap in 0(1) .
I personally like the idea of 1 pass to put in the map and then pass once more over the string and comparing that to the value at that key and if it’s the first value that’s 1, return that key. But I wanna look into your solution. I didn’t know it was a thing
@@tannerbarcelos6880 Here is what i did. Now, i dodnt know how much time it will take, you can calculate and share the findings here.
String sample = "ababcd";
Map sampleMap = new LinkedHashMap();
for (int i = 0; i < sample.length(); i++) {
char c = sample.charAt(i);
if (!sampleMap.containsKey(c)) {
sampleMap.put(c, 1);
} else {
sampleMap.put(c, sampleMap.get(c) + 1);
}
}
System.out.println(sampleMap);
for (Entry entry : sampleMap.entrySet()) {
if (entry.getValue() == 1) {
System.out.println(entry);
break;
}
}
Hash map does not maintain order. So in this case when looping through the map, it’s not guaranteed that you get the first character that has 1 as the value.
First solution that came to my mind was to split the string on each character into an array. Then delete duplicates from it and return the first index or underscore if the array is empty. Not saying it's the best solution, just the first thing I thought of.
Wow this is indeed O(N) time complexity. Though the constant that is multuplied by N here is way larger than the optimal solution.
@@makagyngrimm3392 Wouldn't deleting all duplicates be O(N^2) though? For every letter you'd have to scan the rest of array for the same letter to delete.
@@Daniel_WR_Hart no you dont scan. you loop through the array again
Use 2 arrays of length 26. One for occurance count and other for first occurrence position. After populating these arrays just find the char with occurrence count 1 and minimum first occurrence. It'll give O(n+26) which will better then O(2n). I know both are equivalent to O(n) but for large n, it'll make much difference.
I consider O(2n) = O(n)+O(n) and O(n+26) = O(n) + O(1)
I love your videos man. So helpful. Another solution that’s better than brute force but isn’t as good as the optimal is to sort characters O(nlogn) and compare the characters next to each other
Won't that alter the first occurrence? Say you have "bccca". When you sort you'll have "abccc".
@Harsh Mehta That could work if the mapping was ( old index : new index ). Then you iterate using the new indexes by retrieving them from the mapping by calling the old indexes from 0 to n. Then all you'd have to do is compare both adjacent elements.
for(int oldIndex=0;oldIndex
I thought of something else. For each letter put you find it has a duplicate put it in an array and precheck each character if it exists in the array then proceed on. If all goes well it will return the requested character. But ik your way is way more effective since arrays take a lot of space in memory and the process will be slower cuz you'll have to precheck everything with an extra for loop. I need to be more comfortable with using boolean lol
I have combined his way and your way actually. Have an array of 26 counters (made them int8_t or char because you only need to distinguish between 0, 1 and >1, you don't need specific count when in >1 case) and a string of capacity 27 which is appended the first instances of each character I encounter (capacity 27 so I also have a NUL terminator).
After the string is done I loop through the second array and use the first one to stop at the first character which has a count of 1 rather than >1. Then if this loop finishes I will return the '_'.
Question from a beginner: what if the string were to be not listed in alphabetical order, and mixed?
that wouldn’t matter at all, if we are searching through the entire list and mapping it the order does not change anything
I think a better solution is instead of storing the count store the index you found the character at initialized as -1. When you see a character update the -1 to the index or if it's already not -1 remove it from the hash map. At the end just loop through the hash map looking for the lowest value that isn't -1. This is much closer to actual O(n) for along strings as the second loop you only need check max 26 keys. If you want to get even more efficient you can still do your method when the number of keys is greater than the length of the string.
I understood the question differently. I would think a non repeating character is not the same as a character that only occurs once.
For example in abbac I would say a is the first non repeating character, even though there are 2 a, I mean it doesn't repeat, there is a b after the a.
Most recruiters appreciate it if you ask questions to clarify the task.
It’s worth mentioning (but not coding) the O(nlog(n)) solution too. If we sort the array, then repeating characters are next to each other. Then we can use two adjacent looping pointers, curr: one that stores the current character it sees, next: for the character at i + 1, and a third variable for running tally. If the next character identified by the pointer is a different character and the tally == 1, return arr[curr]. If we reach the end of our array with the next pointer and it’s equal to arr[curr], return our “_”. This is constant space and is a legitimate tradeoff vs a constant time, linear space solution, though we usually prefer faster time over lower space. Writing the sort function for characters can be annoying too, taking up about 10 minutes. On a real interview, you want to mention all of this, then get to writing the code for the solution that you can reasonably implement in 30 minutes.
Bro, i have seen many videos for competitive programming and none of them explained the solutions or even the questions this way. Keep up the good work. Your videos really helped me a lot. 😊
A better solution could be O(n + 26) = O(n) [lower than your O(2n) = O(n)], by just having the same 26 size array indexed by the number of the letter as you explained, but instead of storing the count you could store the index where you first found the letter, if during the traverse you find that there is a repetition then set the index as -1. After finishing the traverse, just check the 26 size array and find the lowest index in there, if all of them are -1 then there the answer is "_"
HashMap is a wrong choice. Hash map doesn't guarantee the order of insertion. You need to use LinkedHashMap if you want to preserve the insertion order in java.So in your example at 8:50 , it may give you d or f, if you are using normal HashMap.
hashmap is fine here
we’re not looping through the hashmap which i explain in the video we’re looping through the string once again and doing lookups to fine the first character that has a frequency of 1
hashmap will do just fine
Shery's right - HashMap doesn't guarantee the order of insertion (www.geeksforgeeks.org/differences-treemap-hashmap-linkedhashmap-java/). The Python OrderedDict guarantees the order of insertion (docs.python.org/3/library/collections.html). Here is basically the above implementation using OrderedDict -
import collections
from collections import OrderedDict
def firstNonRepChar(inpStr):
odS = OrderedDict()
for c1 in inpStr:
odS[c1] = odS.get(c1, 0) + 1
for c1 in odS.keys():
if odS[c1] == 1:
return c1
return '_'
This one is obviously doable as O(n): Two 26-element arrays, one (count) initialized to 0, the other (first_seen) to MAX_INT, then loop through the input, starting at the back end!
do {
c = inp[--pos] - 'a';
count[c]++;
first_seen[c] = pos;
} while (pos);
Afterwards we just do the constant-time scan of those two arrays looking for those with count==1 and first_seen as low as possible.
For extra credit write a SIMD version (somewhat hard to make efficient). A GPGPU would actually be more straight-forward. With really large inputs we could do a multi-threaded version with a reduction step/merge of the partial results at the end, this should easily be able to saturate the memory bus.
Nick white is by far the most legit channel for preparing for coding interviews...thanks dude for making this channel a full fledged community...
Fact: The HashMap solution is considered O(n) space as number of inputs isn't fixed, while the frequency array[26] approach is O(1) space as range of input is predefined, what's funny is the HashMap might actually use less space than the frequency array, as the frequency array also has to allocate space for non occurring characters.
The most simple and straight forward explanation you could find for this question,
Can you provide the code for all 4 approaches using C.
Second method of using 26 array elements will not work for input like “azavbb” (seen in this video at 1:00), as it will have 1 for both ‘z’ and ‘v’, when we scan array to check for first element with 1, we get ‘v’ but correct answer in that case is ‘z’ as it is the first non repeated letter when scanning from left to right.
What's stopping you from creating a second hash map with key value pairs of first indexes, meaning a: 0, b: 1, c: 2 etc
Hi Aleks, you are likely to have a key more than once which violates the building components of hashmaps and won 't be efficient for what you are looking for
@@brianotienotruimp how can a hashmap/dictionary key get violated?
Aleks D you can’t have the same key twice
@@brianotienotruimp you're not going to have a key more than once as you'll check to see if the key already exists.. if it does simply add to the increment for that letter.
you dont need to even use a hashmap. you can use the ascii code of a char as a direct index in an array:
intarray[(int)string.charat(y)] gives each character a unique position in the array. The int values of chars a-z is 97 to 122, and you can cast a char directly to an int.
public char firstnonrepeating(string searching){
// index in this array will be the ascii code of each char, value the count
int[] found = new int[122];
// index in this array will be the ascii code of each char, value the last index
int[] lastpos = new int[122];
for(int j = 0; j < searching.length(); j++){
found[(int) searching.charAt(j)]++; //count each character
lastpos[(int) searching.charAt(j)] = j; //store the last index of this char
}
int position = searching.length();//keep track of the
char found = '_';
//the array will contain all counts, find the one with the smallest position
for (int i = 97; i
You can actually do it in a single pass if you store the position of the character. Also: you don't need to store the count, just the flag whether it occurs more than once.
Just joined Bachelor's in CS.
At first thought I know that it can be done in two ways ,
•First by nested loop , by checking every index, but I know that it will take more time. (Once I got similar problem in Programming contest. I did it by looping, but I got TLE. So later I got to know about Hash Map)
•Second we can do it by using hash map.
This is the first interview question that I have seen that actually has some real world use.
Where would it be used? Not doubting you I'm just curious
@@marttielvisto3519 ^
NonRepeating and Unique does have a different meaning right? My first (as non english native) was just lookAt [index+1] XD lol
I guess it doesn't specify whether or not they have to be "directly repeating" or just "repeating" within the string. I agree though that "Unique" would be a better term to have used.
Without looking at the video (so his solution may be better than mine).
Put the characters into a LinkedHashMap where the key is the character and the value is the total occurrences of the character in the string.
Then, remove any element from the map with a value higher than 1.
Then, return the first of the remaining entries on the LinkedHashMap.
(Note: It is important to use a LinkedHashMap since it keeps the order in which the elements were inserted)
I tried this myself before watching solution. Took me like two hours to create this 60 rows long monster that somehow actually worked, but then I played the rest of the video and couldn't believe how easily it can be solved 😂
You'll get better keep practicing
60 rows for what??
That last solution, where you compare indexOf() to lastIndexOf(), is not O(n). Since both indexOf() and lastIndexOf() both need to loop through the string, and you're calling them on each iteration of the outer loop, you're back to O(n^2), so while the code looks much cleaner and I would prefer it in a situation where string lengths would be guaranteed to be small, it is worth pointing out that it is not an optimal solution in terms of time complexity, and probably wouldn't pass an Amazon interview.
That intro, the baggy shirt, the monotone. Oh no it’s the coder kid starter pack.
Proposed solution=
create empty seenArray
for each letter, determine if it is already in seenArray,
if it doesn't already exist, push letter onto [end of] seenArray,
if if does exist already, remove existing letter from seenArray (don't add current letter to seenArray)
proceed to next letter for sample.length-1 times
once end of sample is reached, return seenArray[0]
Note: I just discovered your channel and I like the content so far. Great job! My software development experience is limited to a few projects and the first few sections of freecodecamp. I haven't covered data structures yet but I've seen a few videos touching on the topic. I still immediately think of stacking with arrays. I could be wrong here but this method seems worth mentioning as I think it should be O(n) with limited space. I'd love it if someone schooled me if I'm misunderstood here. Looking forward to the rest of your content, Nick! keep it coming.
Your proposed solution sadly won't work, for example, it will return 'a' for the input string 'aaac'.
Your video on "How to Crack Google Interview (Complete Guide)" is now private.
Can you please post it again. It would be really helpful.
Loop through the string with with a for loop --> use the method "lastindexof" with your current character. If the index that the method returns is equal with your current index than the character doesnt repeat. Thats the first solution that came into my mind. And you only have to loop through it once.
Should wait till the end before commenting... lol
Just abt to do this Q n saw urs！ Awesome dude！
So it was spoiled for u
great vid, there 's an option to use insertion ordered data structure (like dict in python or vector in cpp) and increment the keys after their value passes 1-->O(n)
This was similar to my first thought. Define a queue containing characters you've only found once, and as you find a duplicate character, take it out and move it to a set containing characters you've found more than once. I believe that solution is O(n) as well, and it's nice that we don't have to worry about counting. I think I still like the int array solution the most, though.
how tf are the interview questions this easy!?
unless they specified what job this is for a coding interview can range from all sorts of coding related jobs, you definitely don't need much more than this if you're just going to be doing some assistance or something
normally this is a warmup type question. You'd be shocked how many people can't solve a problem like this in linear time.
@@doggo660 I hope so!
This was still not an optimal solution. 2 integers could be used to store all of the needed information in their bits. Also, providing information about the actual complexity of the HashMap, which is constant, but not 1, would show that you are a more advanced developer.
@@dzramen Could you elaborate a little? Or may be give a link to your solution on leetcode?
Hey, buddy. In your first "brute force" example you don't have to start with j=0. The situation here is similar to bubble sort, where second loop doesn't need to look for previous elements, because they were handled in previous loops, so make it j=i++
Instead of looping through the entire string a second time to find the first unique char, take the index of the first 1 in the char counts array, add the ascii code for 'a' and that's your character. Would be faster as you only have to loop through 26 chars at worst.
That would return the front-most letter of the alphabet that occurs once. Not the first letter in the original string that occurs once.
Why the second loop over the string? You could record the index in the hashmap instead of the times it occurs, and if it occurs more than once, replace the index with -1. Then, loop through the keys of the hasmap and record the lowest index.
I wanted to ask bc my friend told me about it when interviewing, btw this did help me understand what companies want from someone, anyway my friend told me that if they give u a question u already seen and solved that u should tell them, is that a good idea or no??
I say it depends how well-rehearsed and familiar you are with the question. If you literally know the exact steps, I would be honest with them, but also be clear with the boundary conditions of your solution. Then maybe, they would ask further constraints to the same problem (any good interviewer should do this) or ask a different problem. The main goal of these interviews is to see how well you can communicate your thought processes and divide a problem into smaller/logical chunks under a time constraint. I think the big mistake a lot of people make is going straight to coding without giving a good big picture step through of the problem and how it can be solved. Implementations can then vary.
This solution seems more like it should be "first unique character"
Also in the case of the the array[26] solution, wouldn't it actually iterate alphabetically meaning you would get the "first unique character alphabetically". If all inputs are alphabetically sorted then this isn't a problem but It doesn't specify that anywhere. I think it would be more safe with using the hashmap
No, you dont iterate through the array, the same as you dont iterate through the hashmap. You iterate over the input string only. And with both, hashmap and array[26] you have constant time of getting the value that represents the number of occurrences. In hashmap, you calculate the hashcode, and in the array, you calculate the index with the letters like b - a = 1 for b, d - a = 3 for d etc. Same thing.
When I read Java I understand why people say that Python is more beautiful 😛
his code writing style is trash tbh.
You can do way cleaner than he did, by using foreach loops, or streams
for example :
String s = "aaaabccdeeff";
return s.toCharArray().stream.filter(c -> s.indexOf(c) == s.lastIndexOf(c)).getFirst().get();
or even
String s = "aaaabccdeeff";
for (char c : s.toCharArray())
if (s.indexOf(c) == s.lastIndexOf(c))
return c;
return '\0';
@@notkamui9749 u wouldnt return '_' for the first solution
Java is horrible for reading (or working) unless you really have to work with Java as the company requires, otherwise Python is way better to work and read.
Does programming really matters when solving the problem? What matters it time and space complexity.
Your thumbnail was so good that i did not need to watch the video to get solution, great job man!
"non-repeating" here seems fairly misrepresentative of what you're actually doing given the rules explained. At best, it's super vague. I would prefer the word "unique", myself. I could MAYBE consider "non-repeated"; but "repeating" implies that the letter is the same in the order given. Not really YOUR problem, I guess; and as long as the rules are there it doesn't matter too much. Just seemed weird.
Man you're dumb
I agree that "unique" would be less unambiguous to use. However, "non-repeating" is not necessarily incorrect. I think they consider a character being a repetition of an earlier character to count as "repeating".
Agreed. I initially interpreted the scenario by thinking repeating was only if it was sequentially repeated, not that repeating meant no duplication of a character in the entirety of the string. (Past tense of the verb repeated vs active verbiage use of repeating is interpreted differently in my mind).
I.e. aabcd would return a, but abcabd should also return a as a was not directly followed by another a. So I think first unique character, or first character that has a count = 1, or something along those lines would be better in giving a firmer grasp of the scenario presented.
The third example with the 26 character array wouldn't work. It would return the lowest character in the alphabet non repeating, not the first.
it does work! think about it a little more! passes all test cases and submits successfully
@@NickWhite Is it not only because your string is in alphabetical order?
@@NickWhite I rewatched the video and found, that you are traversing over the string in the second loop. This does work. Sorry
What about this solution (only loops once):
string = list('abacabad')
not_repeating = []
visited = []
for i in string:
if i not in visited:
not_repeating.append(i)
visited.append(i)
else:
if i in not_repeating:
not_repeating.remove(i)
if not not_repeating: # if not_repeating is empty
print('_')
else:
print(not_repeating[0])
>>> c
perfect;
I want you to teach me your sorceries ,Master.
Only one thing ,try doing it in c ,c++,or java
This solution is good if a lot of the characters in the string are not repeated consecutively, or there is not a unique character within the string.
Note: This solution is actually O(N^2) as it loops through a list again, and we have to store two more lists than needed to solve this problem.
@@890popbox dude it loops only once
In the map, first time add the Index value of a character as a value to key (character), and later instead of adding a count of occurrence, just make the value of a key (character) as -1 if it's repeated. Now iterate over unique keys from the map and not input array (so it will be less in number as compared to original string ) and check for lower index character .. here you got the solution.
the new video format is much better
for non-repeating characters, my idea to optimize stuff is just scan the string when finds a letter, after scanning it turns all duplicates into let's say zeroes, that are simply ignored, so if you have aaabccc..., it just scans the entire string once for a and once for c, however i think it would go below O(n*log(n))
I dont know if only Python has count method? In python i would do like this: for loop (for char in string) then if string.count(char) == 1: return char, else string.replace(char,'')
collections.Counter()
You can do it in python with storing occurences in a tuple then turn the tuple into an array(that only takes a value once ) and make it print the first corresponding character from the string that has occurence equal to 1
Why not create a second array that populates with the letter found for each new index position and then loop through the first array (the one with the number of hits) the second time instead of the entire string? You'd only have a maximum of 26 items to loop through in the array as opposed to the possible 100,000 duplicate characters in the original string. Once you find the first index with a 1, you check the second array for the letter that was originally found for that index position.