Amazon Coding Interview Question - firstNonRepeatingCharacter

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-developer-academy
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nickwhite
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow Me on X/Twitter - x.com/nickwhitereal
Follow My Instagram - nickwwhite
Other Social Media
----------------------------------------------
Discord - discord.gg/ZGyc2nZyAx
Twitch - www.twitch.tv/nickwhitettv
TikTok - www.tiktok.com/@nickwhitetiktok
LinkedIn - www.linkedin.com/in/nicholas-w-white/
Show Support
------------------------------------------------------------------------------
Patreon - www.patreon.com/nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - kzbin.info/door/1fLEeYICmo3O9cUsqIi7HAjoin
#coding #programming #softwareengineering

[@EchoVids2u]

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.)

[@blasm1713]

God loves you

[@jinxy7869]

@@blasm1713 shut up

[@blasm1713]

@@jinxy7869 god loves you too

[@nicolas.martiiin]

@@blasm1713 LMAOOOO

[@daemperador123]

Did you get an offer?

[@kumaransg1828]

Your channel helped me a lot to brush problem by watching them over and over, finally got a offer from Amazon thanks a lot

[@techbarikcom]

Great

[@knight_23]

Which position?

[@moritzgro2442]

@@chandud4255 lmao

[@kumaransg1828]

@@knight_23 SDE 1

[@iaashu98]

@@moritzgro2442 joke on you, kid

[@dragosgeorge1086]

The complexity of the last solution (with the builtin indexOf methods) is O(n^2). Those methods traverse the array to find those indexes.

[@Alistair]

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)

[@igornoga5362]

@@Alistair You can also loop over the alphabet instead of whole string, with complexity 26N = O(n).

[@popularmisconception1]

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.

[@billmy2251]

@@popularmisconception1 you mean to take a pair of last and first index for each letter?

[@NathanBLawrence]

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.

[@TheTraveler221]

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

[@micky2be]

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.

[@kouyang1771]

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).

[@dudaseifert]

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

[@gblargg]

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.

[@dudaseifert]

@@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

[@starskiiguy1489]

@@gblargg When storing only ~104B+len(sequence)B in memory it's extremely unlikely storage is a larger concern than speed.

[@gblargg]

@@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.

[@codesling3421]

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)

[@HareendraTejaReddyDonapati]

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

[@RhymesWithCarbon]

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.

[@williamragstad]

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.

[@iippari7]

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.

[@chon-850]

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

[@The5thUSER]

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

[@slathian1223]

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.

[@jajefan123456789]

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.

[@anujramaswamy6809]

@@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 "_"

[@VishalPatel_imvishal]

@@anujramaswamy6809 would this works? You sure?

[@FinBoyXD]

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.

[@ReflectingMe2024]

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 :)

[@huckleberryginesta7941]

why its always important to ask clarifying questions to an interviewer if you're not sure.

[@dmitarzvonimirmitev6644]

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.

[@mammlouk]

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.

[@dmitarzvonimirmitev6644]

@@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.

[@drmangrum]

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.

[@nixalot9065]

THANK YOU!! I was yelling this at the screen.

[@VishalPatel_imvishal]

How would you explain linkedHashMap to the non Java interviewer?

[@MaharshiYadav]

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)

[@yissssss]

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.

[@dawgsout4free]

Instructions not clear I got hired as the CEO

[@wsdookadr]

So you won by failing?

[@jorandebraekeleer7557]

Nice

[@blink182lives100]

BigHead is that you!?

[@PurhanKaushik]

nah, sorry not funny

[@alessandropedrinolla3404]

Task failed successfully

[@edge30]

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.

[@batmansmk]

indexOf is O(n) in all arrays implementation in languages I know. So the last solution, despite being elegant, is O(n^2).

[@aniruddhashevle]

Exactly my point. Hence hash maps/array of alphabets counts could be better than indexOf!

[@awkwardlycharming]

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

[@Krechevskoy]

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 }

[@paulstelian97]

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).

[@Krechevskoy]

@@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.

[@paulstelian97]

@@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)

[@Krechevskoy]

@@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.

[@paulstelian97]

@@Krechevskoy The best algorithm has constant space (input is not considered if treated as read only).

[@DaGamingDragon2]

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 "_".

[@TheDRAGONFLITE]

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...

[@oblivion_2852]

I would use a hashmap where I store the index it occurred at. I would pass over the n values adding elements to the map if a value is already within the map I would set the index to - 1. Then if another element comes up I would know it has already been duplicated. Thus there would be three states; not within, within at index, duplicated. Then I would iterate over the map and find the minimum index and return the character. This would be n time complexity and technically constant space complexity of sizeof(char)*sizeof(int).

[@arky5674]

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

[@satibel]

even if the question was first non sequentially repeating, the first a is repeating since the next character is also an a.

[@sabazillo]

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]

Yea, but as far as I understand your solution you would multiply even 100000 times which would cause an integer to flip.

[@sabazillo]

​@@blazejeczek8710You only have to multiply once per character, but you are right, that could be a problem with really long character strings.

[@sabazillo]

@@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.

[@blazejeczek8710]

@@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.

[@audigex]

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

[@Kiramekushoujo]

This is kinda late but if the string was "aaabcccda" the last 'a' would appear to be non repeating even though it does repeat.

[@Grassmpl]

With "aaab" that would return 'a' since the last a would be counted as nonrepeating.

[@KavasPVP]

In C++ I would turn the letters into ASCII code values in a frequency vector. Then I would check with a for function if there is any position with a value of 1 attributed to it (the non-repeating character). Then I would compare each letter of the string with its corresponding frequency value in the vector. The first character that it gets to which has a value of 1 in the vector will be returned. If there is no such letter with value 1 (either 0 or 2+), then the program would return -.

[@CharlesFlahertyB]

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.

[@geekyvors2837]

A bit late, but split is O(n) so it would be O(n^2)

[@makagyngrimm3392]

@@geekyvors2837 Correct

[@jenesaispas4506]

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

[@bernardobritto8352]

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')

[@Shuizid]

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')

[@bernardobritto8352]

@@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')

[@bruh_5555]

You could do this in O(n) instead of O(2n) we could use a c++ vector of STD::pair and push_back values of the respective letter and value false indicating it is the first time we are seeing it. if the values are already present then assign true to that specific value and then after you're done reading the entire string just iterate over the small 26 elements long vector and return the first value that is false which is non repeated.

[@SocajowaRS]

Love the quality of this vid, a chop above your standard stuff nick thanks for putting in the effort!

[@ExplorerForLifetime]

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.

[@siddhantjain2402]

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.

[@fidelischarles4545]

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.

[@LenaYoutube]

@@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?

[@siddhantjain2402]

@@LenaKZbin 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.

[@fidelischarles4545]

@@siddhantjain2402 well said

[@waisrainy]

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)

[@crud41]

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.

[@VilasNil]

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).

[@crud41]

@@VilasNil good point.

[@seanvinsick]

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.

[@AustinsMind]

I paused the video in the beginning and gave it a quick go in javascript, here is my first solution, for fun I will do it again but using recursion, interviewers seem to love when you know it and know how to use it: let string1 = "aaabcccdeeef" let answer = nonRepeatFinder(string1) console.log(answer) //function that returns the first non repeating character in a supplied string function nonRepeatFinder(s){ //holds already repeated characters so we can skip these when we encounter them further down the string let cache = [] //holds the current character let temp = "" for (let i = 0; i < s.length; i++){ //grab character at the position of the string we are in temp = s.charAt(i) //check if this character already exists in our cache and skip if so if (!cache.includes(temp)){ //create a sub string after the position we are at let newStr = s.substr(i+1, s.length-(i+1)) //see if we get an index with our current character, returns -1 if no index let index = newStr.indexOf(temp) //check our index if(index == -1){ //not found, winner winner chicken dinner return temp } else { //keep looking and add the current character to our list cache.push(temp) } } } //if we get to here then we dont have any non repeating characters return "No nonrepeating characters found" } EDIT: Didnt even know about .lastIndexOf(), that would have cut down a lot of code, but this is why I love programming, so many approaches to take to solve one problem and truly an area where you can learn something new every day!

[@MsJavaWolf]

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.

[@walihasan9155]

def count(variable,x): count=0 for i in variable: if i==x: count+=1 return count a = input("enter the string here") for i in a: if count(a,i)==1: print(i) break

[@shahbazalam4565]

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) ???

[@oblivion_2852]

That's what I thought. I'm very wary of using builtin commands because often times they have their own complexities

[@JohnTrustworthy]

Depends on implementation but in most of the cases yes.

[@quyenv.nguyen6130]

@@JohnTrustworthy You cannot perform better than O(n)

[@JohnTrustworthy]

@@quyenv.nguyen6130 Hash algorithms?

[@Suchoshak]

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).

[@andersoneliezerramirezcarr8143]

About your second solution: First thing I thought about that solution is that it shouln't be neccesary to use the second for loop. Then I noticed that increasing the time every character is repeated with char_counts.put(c, char_counts.get(c)+1) is not helping, because the only thing we need to know is that as soon it appeared twice is not elegible. Therefore you don't even need keys and values, you can use a HashSet instead of HashMap. What you need is second data structure to store the elegible characters sorted, let say a linkedlist, from witch you can remove character as soon you know is repated and retrive the first not repeated character when the for loop ends. char firstNotRepeatingCharacter(String s){ HashSet characterContained = new HashSet(); LinkedList nonRepeatedCharacter = new LinkedList(); for (int i = 0;i < s.length();i++){ Character c = s.charAt(i); if(characterContained.contains(c) && nonRepeatedCharacter.contains(c)){ nonRepeatedCharacter.remove(c); }else{ characterContained.add(c); nonRepeatedCharacter.add(c); } } if(nonRepeatedCharacter.isEmpty()){ return '_'; } return nonRepeatedCharacter.getFirst(); }

[@ShashiBhushan2k13]

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 :)

[@lovelycode7173]

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)

[@cas1652]

Entry set is the string anyway so not sure would be worth.

[@edschaeffer]

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.

[@turn1210]

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.

[@markzamiebarrientos5904]

Nice

[@HeyItsSahilSoni]

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

[@mammlouk]

@@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.

[@harrywang4769]

So iterate over a string 26 times? You would fail my interview

[@backedPOTATOE]

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.

[@backedPOTATOE]

Should wait till the end before commenting... lol

[@JunaidAhmed-jd5kq]

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.

[@Mekelaina]

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.

[@1gnore_me.]

youtube has been recommending me a lot of coding videos lately and I love it

[@LoganMeyers03]

IKR

[@micky2be]

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.

[@micky2be]

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.

[@winnieww]

How I wish I get these problems during interview. I somehow always get maze, graphs problems :(

[@jeffadams1296]

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.

[@MicLo18751]

Your proposed solution sadly won't work, for example, it will return 'a' for the input string 'aaac'.

[@bakutabata8798]

You needed to capture the index to find the first non-repeating character. Your answer assumes the string is in alphabetical order.

[@sfitz219]

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

[@TerjeMathisen]

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.

[@bjorno43]

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]

Wow this is indeed O(N) time complexity. Though the constant that is multuplied by N here is way larger than the optimal solution.

[@Daniel_WR_Hart]

@@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.

[@makagyngrimm3392]

@@Daniel_WR_Hart no you dont scan. you loop through the array again

[@foodice11]

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.

[@satibel]

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.

[@joshcaithness8123]

@@satibel For example dictionaries in Python

[@campermortey]

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

[@JohnTrustworthy]

Won't that alter the first occurrence? Say you have "bccca". When you sort you'll have "abccc".

[@JohnTrustworthy]

@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

[@JohnDoe-iw8mp]

In JavaScript you have a String.split() method. It receives a character as argument, splits the string where that character is found and returns an array of the split elements. Here's my solution using this: const firstNonRepeatingCharacter = str => { for(let chr of str) { let splitStr = str.split(chr) if(splitStr.length === 2) return chr } } What do you think? Does it look optimal?

[@chompyzilla]

split is O(n), so your function is O(n^2)

[@tannerbarcelos6880]

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

[@kolliparachandana]

Tanner Barcelos same here

[@amoghvk5]

you can use linkedhashmap it will sort the keys in added order.

[@tannerbarcelos6880]

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

[@amoghvk5]

@@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; } }

[@cipherxen2]

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)

[@ragingpahadi]

LinkedHashMap can keep the order !

[@maheshtambe9535]

Thanks

[@MrVikram0001]

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.

[@aleksd286]

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

[@brianotienotruimp]

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

[@aleksd286]

@@brianotienotruimp how can a hashmap/dictionary key get violated?

[@brianotienotruimp]

Aleks D you can’t have the same key twice

[@tobyn123]

@@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.

[@zazethe6553]

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

[@jasonhornsby8666]

Question... Why would you have to loop through all the items if you are ony interested in the first occurrence? Start one loop over the characters, remember the char last_char and a bool seen_before initialized on false. When the current char matches the last char set seen to true. If it doesn't, check if seen is false, if yes return last_char else set last_char to current char and set seen back to false. This would have an worst case complexity of at most O(n)

[@wyk6318]

this video is more “phone user” friendly than the previous ones. Love it!

[@WaveTVsubscribe]

yikan wang get a computer broke ass

[@jackytaly]

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

[@wyk6318]

Jack haters gonna hate. My laptop is above 1k. I brought KZbin 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.

[@chiragsingla.]

For some reason I code on my phone and not in pc most of time

[@maciejzwolinski2381]

You can reduce the search time from O(2N) to true O(N) VERY easily: 1. when you create 'counting array' of size 26 fill it with '-1's or 'sizeof(input_array)+1' 2. when looping through the string save the index of the letter to an appropriate entry if that entry is '-1', else set entry to '-2' 3. loop through the 'counting array' once returning lowest non-negative index (turned to appropriate char) or '_' if non were found

[@sercancelenk7131]

Question from a beginner: what if the string were to be not listed in alphabetical order, and mixed?

[@jlacr8056]

that wouldn’t matter at all, if we are searching through the entire list and mapping it the order does not change anything

[@ElZedLoL]

So on the brute force your yellow arrow doesnt have to start before ur index. Sure, its still n(n+1)/2 = O(n^2) But in this solution you may also have an array with characters you already checked for and are going to skip with ur red arrow. But sure a record/map do be better

[@poojaguru2516]

Awesome, the way you explain makes programming even more interesting🔥

[@cibureh2684]

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.

[@AnkitKumar-ow6fg]

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. 😊

[@anibaldk]

Not a bad solution but it implies going through the big array twice. You could have a hashmap where the value is a tuple (character, first_occurrence, amount). After the run on the big array, you simply: 1- Get all values from the hashmap 2- Filter those where amount == 1 3- Get the one with the minimum first_occurrence It would be a loop on max 27 items for the filtering and then a couple for the min operation.

[@adityagoswami6881]

The most simple and straight forward explanation you could find for this question, Can you provide the code for all 4 approaches using C.

[@sindyr]

Amateur coder so I may be WAY off, but it seems to me that this would be the best solution, because you would only have to loop through a single time. The pseudocode: Create two empty strings, DUPES and SINGLES Loop through the target string character by character. For each character: >Does it exist in DUPES? Then skip to next character loop. >Does it exist in SINGLES? Then remove it from SINGLES but add it to DUPES, and skip to the next character loop. >Append the current character to the right END of the SINGLES string. Loop to the next character. Now the leftmost character in SINGLES is your answer. If SINGLES is empty, return the underscore. Wouldn't that be the fastest? An O of N, perhaps?

[@ZeroSleap]

The naming is a bit fail,i'd suggest the function be named firstUniqueCharacter

[@jamoinmoin]

Exactly my thought. The name suggests "aabaabbb" would return b, but in this solution it wouldn't.

[@jasperdiongco4668]

Yeah, I agree with this.

[@e_tas_]

Except there's already such a thing as a "unique character" such as $, &, #, @, etc. It's supposed to be as clear as possible.

[@inordirectional]

@@e_tas_ Never heard anyone refer to non-alphanumeric characters as 'unique characters' though. Nonrepeating is clearly ambiguous, unique is less so.

[@e_tas_]

@@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)."

[@JohnTrustworthy]

Another way to bring O to n from 2*n is to pushBack all chars with occurrence of 1 in a list and when their occurrence becomes 2 you tell the list to remove object which will have complexity of max(26) for the remove and linear for the integer array. Then you just popFront from the list.

[@K_R_N.]

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.

[@makagyngrimm3392]

That would return the front-most letter of the alphabet that occurs once. Not the first letter in the original string that occurs once.

[@miri669]

Map implemented as an ordered list of int32 values, with additional array (size 26) of pointers to list elements that are counts for specific characters. When character is encountered, we check the array (array[0] = pointer to count for A, array[1]=pointer to cound for B) to see if it was encountered before (array has pointer), if so, increment the count in the list, if not, create a new list node at the end, set count to 1, save pointer in array, . This way, the "map" is sorted, and only needs O(26) instead of O(n) to find the actual first non-recurring character after completing the map. We paid for it by minimal extra code, and 26 pointer-size array. We can extend the solution if we decide to extend the possible values (you would have to adopt ASCII/Unicode mapping for Array, depending on the possible values list) or string length (int32 -> int64 -> bigger data type).

[@debajyotiroy6843]

Nick white is by far the most legit channel for preparing for coding interviews...thanks dude for making this channel a full fledged community...

[@Altirix_]

would a faster way be to instead of storing the count of each character in the hashmap, rather store the first index the letter is found, if the hashmap is already set for a char, set it to null or -1, then rather than loop over the string again you search the hashmap for the lowest index and thats your answer. id assume this would be better for larger strings so now aaabcccdeeef = [a = -1 b = 3 c = -1 d = 7 e = -1 f = 11]

[@dreinax]

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 😂

[@ipodtouch470]

You'll get better keep practicing

[@dj_b1627]

60 rows for what??

[@victorolin5020]

Why would you loop through the string again after you've created a hashmap/an array of key-value-pairs when you can just loop through the array and check for the first 1 among the values? You'll save potential double look-ups.

[@kunal_chand]

Your video on "How to Crack Google Interview (Complete Guide)" is now private. Can you please post it again. It would be really helpful.

[@samh9754]

May be a dumb question, but why use a hashmap to keep count? My solution was to begin by creating an empty array called "repeaters". Then, for each character in the string, I first check to see if that character already exists in my "repeaters" array. If it doesn't, I then count how many times that character is located in the original string. If it's more than once, I append that character to my "repeaters" array. The first time I get to a character that does not appear in the repeaters array and has a total count of "1" in the original string, I know I have my first non-repeater. So I return it. I'm a bit new to the whole "N^2 and O of N" concept. Is my method slower? I just don't see the point of needing a key, index pairing. Who cares if the character is in the string 16 times? The second I see it twice, I know it's a repeater. So why keep counting?

[@goplayer7]

For the last solution isn't the time complexity of indexOf/lastIndexOf O(n) internally [given that the pattern in this case is of length 1] meaning the entire solution is O(n^2) making it worse than the earlier solutions?

[@husainzafar3445]

The question asks for first non repeating character. Are we instead trying to find a character that appears just once? "aaabbbcdddeeec" -> should return c but if we do a sum, we might not get any answer as c occurs twice

[@babumon5351]

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.

[@NickWhite]

hashmap is fine here

[@NickWhite]

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

[@nishthavan3764]

hashmap will do just fine

[@nitchow]

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 '_'

[@brandonallen2301]

Just did this problem earlier today. Fun fact dictionaries (at least in c#) are ordered if you loop through with a kvp, so you can just find the first value in the dict that's 1. Stil O(2n) though

[@JOELwindows7]

This is your daily dose of Recommendation .

[@alexluz321]

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]

what about the time required to traverse the list...i am bit confused...can u explain the time complexities involved in it

[@alexluz321]

@@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.

[@shrikantwankhede8317]

@@alexluz321 okay....got it , thanks for replying

[@irustv7674]

firstNonRepeatingCharacter by python: x = 'azavbb' for i in x: if i not in x.replace(i,'',1): print(i) break

[@Mr1995Musicman]

Remember that checking whether a list contains an element is a linear operation, this is sneakily O(n^2) A more direct translation of his code would be this counts = {} for char in string: counts[char] = counts.get(char, 0) + 1 for char in string: if counts[char] == 1: return char return '_'

[@janikcodes]

havent seen the answer yet but I think i got it. 2 Dimensional List with string, int. string = to the character and int the amount of times it appeared in the long string. Then I simply loop trough the long string, add each unique character into the list. If a character appears twice or more, I check the list and ++ the int. In the end I simply check what was the earliest value with the int = 1. That makes sense for me. EDIT: After watching the video I realised he did excacly what I wanted to do

[@rc3043]

NonRepeating and Unique does have a different meaning right? My first (as non english native) was just lookAt [index+1] XD lol

[@lleytonmorris6305]

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.

[@TheTraveler221]

you can implement this problem with O(N) solution without the 2, with a hashmap and a list where the hash object is a pointer to the list and when you pass through a new element you add this element to the list and the pointer to the hashmap, and if you repet this element you can access this object end deleted from the list so when you finish your array of charecters, you will only have on the list the elements that aren't repeted, and the first one will be your answer.

[@tommi1654]

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

[@amirberkani8492]

perfect;

[@torontoTamilan7]

I want you to teach me your sorceries ,Master.

[@torontoTamilan7]

Only one thing ,try doing it in c ,c++,or java

[@890popbox]

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.

[@amirberkani8492]

@@890popbox dude it loops only once

[@coreynorlander5596]

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.

[@Lokoislive]

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??

[@CknSalad]

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.

[@skillato9000]

Def es1(string): Answer = [ ] Check = set() For i in string: | If i in Answer: | Check.add(i) | Answer.remove(i) | If i not in Check: | Answer.append(i) | Else: | continue If Answer != [ ]: return Answer[0] return "_" Would this Algorithm also do the trick? Or is it slower?

[@eimantasg2055]

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,'')

[@skyisblue3847]

collections.Counter()

[@PrevalentAA]

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

[@HughvanZyl]

I did this in python before watching the solution, I'm pretty proud of my self that i got one of the solutions. def firstNonRepeatingCharacter(string): dict = {} targ = '' for char in string: if char not in dict: dict[char] = 1 else: dict[char] += 1 for i in dict: if dict[i] == 1: targ = i break else: targ = 'No non repeating characters found' return targ

[@HarishKarthik]

Since you're using dictionaries, your code gives wrong answers at times So i used lists and it works perfectly """Here's the code""" def firstNonRepeatingCharacter(string): letter=[] count=[] targ = '' for i in range(len(string)): if string[i] not in letter: letter.append(string[i]) count.append(1) else: b=letter.index(string[i]) count[b]+=1 for i in range(len(letter)): if count[i] == 1: targ=letter[i] break else: targ = 'No non repeating characters found' return targ a=firstNonRepeatingCharacter("hoello") print(a)