First Unique Character in a String

For business inquiries email [e-mail] One of Amazon's most commonly asked interview questions according to LeetCode.
Coding Interviews First Unique Character in a String (LeetCode) question and explanation.
This interview question is commonly asked by the following companies: Amazon, Facebook, Google, Bloomberg Microsoft, Goldman Sachs, Apple, Yahoo.
Problem description: Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
Support me on Patreon: / kevinnaughtonjr
Follow me on GitHub: github.com/kdn251
Follow me on Instagram: / programeme
My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi Discord: bit.ly/K2-discord

[@rajatsemwal1865]

LeetCode should hire you for giving solution to every question. You give so clean and understanding answers that anyone can understand!

[@ezdoesitnow]

So I'm watching all your leetcode videos from the beginning and this being the 3rd video after the 'valid anagram' where you used an 'ascii' array and incrementing that, I was able to apply that approach to this problem. The runtime from that approach was far better and faster than my previous 6-8 submissions for that problem. I can't wait to see how I will be after watching all of your coding videos! Thanks!

[@AwesomAJ]

Love the playlists! You can do this slightly more efficiently without using a counter, just find the first elem in the hashamp that isn't -1 while looping through the string

[@KevinNaughtonJr]

Thanks AJ :) good point, nice optimization!

[@vishalbahedia6720]

If the string length is 1000 and the last character is the answer, then we need to iterate whole string by your approach, but with the hashmap, we will only need to iterate max 26 times at max (assumption that string only contains 26 English characters), no matter what is the size of the string.

[@Garensonic]

Also, the HashMap solution has O(n) space complexity. We can bump the space complexity to O(1) by using an array of 26 elements to hold the character counts: This is the O(1) space solution: public int firstUniqChar(String str) { int [] freqTable = new int [26]; for (char c: str.toCharArray()) { freqTable[c - 'a']++; } int count = 0; for (char c: str.toCharArray()) { if (freqTable[c - 'a'] == 1) return count; count++; } return -1; }

[@vishalbahedia6720]

Even the hashmap solution will not store more than 26 elements in the worst case. So it seems it is same as using an array of 26 elements.

[@blasttrash]

@@vishalbahedia6720 exactly

[@thekomodude]

This comment should've more likes. Clean and concise solution

[@CarlosRomero-ef4uv]

Also i dont think hashmap is O(N), what does N represent? N is input size, what if all chars are a's? then our hashmap would only have one key, worst case its size is 26 entries, and never more unless input is invalid.

[@treyquattro]

except there was no guarantee in the problem description that we're dealing with only upper or lower case English alphabet. What if your string is Unicode or Unicode-32? If the string is guaranteed to consist only of a limited alphabet then yes, this solution is marginally preferable. Your solution can be optimized: you only need to run through the frequency table, not the entire string (which could be gigabytes in length), which is essentially what Kevin did in his solution.

[@pradiplamsal1403]

Hi Kevin, Instead of looping twice, I think you can just loop once from the back and maintain a variable that holds the latest unique element’s index and keep updating that.

[@mannyshapir2685]

Hey Kevin, great solution but I was wondering why in your second loop you don't just iterate over your string (in order since you start from 0th index) and check if the map contains a key that doesn't map to -1 and return the index.

[@kaleemullahnizamani7436]

Because HashMap does not maintain key insertion order, use LinkedHashMap which preserves key order like,

[@docelyk]

The hash map doesn't need to be in order if you are looping through the characters of the string. The characters of the string are in order. You would access the hashmap key by the character and get the index if it is not -1. That way in best case, the first character is unique and you return the index and you've only gone through the loop once. Worst case is of course looping through the entire string twice. If the string was "eeeeeeeeeeeeeeeee" you would need to loop that twice. In the solution in the video that would reduce to a single entry in the hash map

[@snake1625b]

i did it in a way such that the value in the hasmap is an two element array of the frequency and the latest index. so "lle" would be {l: [2,1], e:[1,2]}. however this wouldnt be optimal since im using O(n) extra memory right?

[@palakshah3379]

Hi Kevin, Would you be able to suggest any similar course in C# for Amazon SDE?

[@aashrith95]

Hey @Kevin Naughton Jr. I wanted to ask why did you use a hashmap over a linkedHashmap because hashmap does not maintain insertion order. So if two characters occur only once, it might not maintain the insertion order

[@KevinNaughtonJr]

Right hash maps don't maintain insertion order so that's why I have the second loop iterating over the keys looking for all values greater than -1 and less than our current min. Honestly I don't have a particular reason why I don't use a linked hash map here I'd have to learn a little bit more about how they work to make sure they're not incurring too much overhead cost to keep the items in a particular order.

[@g_455]

@@KevinNaughtonJr No LinkedHashMap isn't so much more expensive than a HashMap, LinkedHashMap uses a linked list which links all the entry sets in the Maps in the order of insertion of a Key, Value pair (the very first time)

[@ilanaizelman3993]

Please continue posting videos. U R AWESOME

[@KevinNaughtonJr]

Haha thanks and I will don't worry :)

[@PShyamSundar1991]

We can try like for( int i=0;i

[@PShyamSundar1991]

This approach is good ?

[@chemilmk8361]

legend, you make going through these bearable.

[@KevinNaughtonJr]

Thanks Chemil!!! :)

[@ridhwaans]

for the latter part, can you alternatively run a built in sort on the maps key collection and return the lowest (at index 0)?

[@ConradCreel]

even if it's built-in, it isn't free. Takes your O(n) to O(n lg n)

[@vinayprasad8196]

+1 with @Siddhartha Thota. First of all - Kudos to you Kevin. Its a great work you are doing in you channel. It is helping me a lot Coming to the approach : Even i was thinking the same, since we need to give back first unique letter, why dont we use the logic of second for loop with the string itself and just check in map if it is equal to 1 and just return that index. Code below, Does not make much difference on runtime , but makes it easy to understand and a clear solution based on the ask. Also we get the answer sooner instead of looping whole map class Solution { public int firstUniqChar(String s) { if(null == s || s.isEmpty()) { return -1; } Map charMap = new HashMap(); for(Character c : s.toCharArray()) { charMap.put(c, charMap.getOrDefault(c, 0) + 1); } for(Character c : s.toCharArray()) { if(charMap.get(c) == 1) { return s.indexOf(c); } } return -1; } } What do you say for this ???

[@celinks123]

Why don't you just use an int[] instead of the Map.

[@mayanktripathi3915]

Can we use array to store the frequency of characters.What i guess time complexity will be same in both cases and using array is more memory effecient than hashmap.Please provide your feedback on this.

[@lBurn38l]

i think the thing is that you can't really use arrays because you don't know how many different characters you have in the string before iterating over it

[@PrimalWildfire]

I am assuming leetcode is using lambdas of some sort to test your code. If so maybe the standard deviation in the performance is due to noisy neighbors in the environment.

[@abhireddy8164]

There is voting happening in a college to select an amendment, total 16 professor and there are 4 groups each group consists of 4 prof and for an amendment to be selected it should be, first selected atleast by a single professor in each group and finally select the one which appears maximum times. I gave a solution and then we discussed my solution and asked me to optimise it further with o(1) memory and o(n) complexity.//sir how can we approach this problem .Thanks in Advance from #INDIA.

[@harikamisetty]

I think we can do this without Map. Like use int[] counts = new int[26]; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); counts[c - 'a']++; } for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (counts[c - 'a'] == 1) { return i; } }

[@Garensonic]

Why do you need to check whether map.get(c) is less than a minimum value? This is how I solved it: public int firstUniqChar(String s) { LinkedHashMap map = new LinkedHashMap(); for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); if (!map.containsKey(ch)) { map.put(ch, i); } else { map.put(ch, -1); } } for (char c: map.keySet()) { if (map.get(c) >= 0) { return map.get(c); } } return -1; } I used LinkedHashMap instead of HashMap, because I know that with LinkedHashMap characters are guaranteed to be inserted/iterated in the exact order they were inserted, and HashMap does not necessarily do this.

[@KevinNaughtonJr]

Nice! I used it to ensure that I return the first unique character. If there are 2 unique chars in the string I need to make sure I return the first one!

[@pradyothcherry3426]

Hey!,Im Just New to Programming .Can You Tell me how your code will run if their are multiple unique characters ?

[@harsh9028]

I think the solution you provided is quite complicated. You could just have looped again on the string and return the first character from map whose count is 1. Looping the hashmap doesn't guarantee that order is maintained so no guarantee that it returns the 1st character which was unique. Good way to do this is looping through string again.

[@rahulchaurasia2069]

Hii Kevin can you please tell me that how can I clear the coding round of Amazon campus placement and also tell me from where I learn ds and algo and also from where I should practice ds and algo questions .tell me the best online coding platform.

[@KevinNaughtonJr]

Hey Rahul, I def recommend using LeetCode to prepare...if you want specific help preparing check out my Patreon page where I have tiers to help people get ready for technical interviews: www.patreon.com/KevinNaughtonJr

[@philbowden]

Hi Kevin Really enjoying your Daily Byte! Instead of storing the index of the characters, what do you think of storing the number of occurrences of each character as the value of each Map element? Then you just have to loop through the string a second time checking for the first character with a value of 1 in the map. This solution passed your test cases, however, let me know if you see a flaw in this approach.

[@jainayak666]

How do you know which is the first element in a HashMap?

[@philbowden]

Hi, it's been a long time since I wrote that comment.. but I think that I was thinking about looping through the string twice. First storing the characters as keys and number of occurrences as values in the Map. Then on the second loop through the string you go until you reach the first character with a value of 1

[@Siddarthathota]

The question asks for first Unique character, what if I have Hello World. Hashmap doesn't save these characters in a row. Maybe the second loop needs to happen on the string itself and search with a specific character and return if map.get(c) == 1.

[@KevinNaughtonJr]

Hey Siddhartha, I'm not sure I understand. The second loop here is just used to find the 1st unique character. It does so by setting the min variable to the smallest number that is greater than -1 (-1 means that character is not unique). I hope that makes sense? LMK your thoughts!

[@vinayprasad8196]

@@KevinNaughtonJr +1 with @Siddhartha Thota. First of all - Kudos to you Kevin. Its a great work you are doing in you channel. It is helping me a lot Coming to the approach : Even i was thinking the same, since we need to give back first unique letter, why dont we use the logic of second for loop with the string itself and just check in map if it is equal to 1 and just return that index. Code below, Does not make much difference, but makes it easy to understand and a clear solution based on the ask class Solution { public int firstUniqChar(String s) { if(null == s || s.isEmpty()) { return -1; } Map charMap = new HashMap(); for(Character c : s.toCharArray()) { charMap.put(c, charMap.getOrDefault(c, 0) + 1); } for(Character c : s.toCharArray()) { if(charMap.get(c) == 1) { return s.indexOf(c); } } return -1; } } What do you say for this ???

[@treyquattro]

@@vinayprasad8196 why didn't you just increment the index in the last loop rather than calling indexOf() which will just run through the string a third time? You already have the info.

[@aribasiebel]

This last for loop can be iterated over the string chars (rather than the map keyset) and just look for 1 in the map. That's your 1st unique character. This soln is from 4 yrs ago so today's Google (non impostor) Kevin will probably agree with this updated soln.

[@plzdntsndmestuff]

Hi, can someone please explain this line of his code: min == Integer.MAX_VALUE ? -1 : min;

[@ashokhari5910]

@plzdntsndmestuff Its a ternary operator which is checking if all the keys maps to -1 (which indicates that every character has repeated occurrence) and we have to return -1 in that case else we have to return the least key value which is pretty much non repeating first character, thanks

[@algorithmimplementer415]

@Kevin Naughton Jr. Could you make a video on prison cells after N days? #Leetcode

[@KevinNaughtonJr]

Just added it to my list, thanks for the suggestion!

[@shivamshah431]

I stored the frequency in hashmap and iterated again over the string to find the first element with frequency 1.

[@rohitaggarwal9789]

You are inspirational

[@rockya742]

Hi Kevin or Other experts here, I see that the method return type is int, but the objective here is find the first unique character from a given String, right?

[@KyuriousBot]

the method type should match the datatype of the returning value. In this case, we are returning an integer value which is an index value

[@rafatashraf3669]

Thank you thank you thank you

[@mohakchaudhary1981]

Excellent explanation. But can u please increase your video sound?😅😅

[@KevinNaughtonJr]

Thanks Mohak! I think the volume is better in my more recent videos :)

[@bhargavideshpande9598]

@kevin could you make a video on critical connections in a Network?#Leetcode

[@KevinNaughtonJr]

yeah i've got that one on my list

[@bhargavideshpande9598]

@@KevinNaughtonJr Thanks!!

[@ArpitDhamija]

nice explainedd

[@KevinNaughtonJr]

thanks!

[@mtr2936]

You can do with problem using constant space

[@kgourav01]

If you are using for loop why hashmap then its not efficient code I think. Instead my logic would be just taking string in char array n check in forloop one by one....when any letter which gives count not more than 1 thats first unique integer.

[@surichirra]

It is good idea to loop over String rather than map. public int firstUnique(String str){ HashMap hm = new HashMap(); for(int i=0;i

[@sandipl3431]

We can do it without using a Hashmap. Let me know your thoughts on this. class Solution { public int firstUniqChar(String s) { for (int i = 0; i < s.length(); i++){ char current = s.charAt(i); if (s.indexOf(current) == s.lastIndexOf(current)){ return i; } } return -1; } }

[@antonstarostin4876]

I'm not Kevin, but I guess I can share my opinion on this. IndexOf and LastIndexOf methods perform a linear search, so basically you doing a search in O(N^2): O(N) for the loop + O(N) for the lastIndex of. Basically, 2 loops would be slightly faster than this solution. I hope it helps.

[@skm9865]

its runtime is 21 ms and kevin's code runtime is 18 ms .considering the length you code is better . thank you

[@ConradCreel]

@@skm9865 hahaha. Okay, run it on a stream of a billion characters and compare.

[@skm9865]

@@ConradCreel True bro , but it's for coding interview preparation not for a project.

[@anilmirya8354]

15ms - leetcode.com/submissions/detail/264779168/

[@PristinePerceptions]

I am sorry to say, but iterating over a keySet actually makes this solution wrong, despite it passing all test cases, because a set is unordered. I would say that either you got incredibly lucky this time or that Leetcode doesn't have strong tests for this problem or both. You should iterate over the input string instead of the keySet to maintain order.

[@vikramkhalsa]

He doesn't need to maintain order because he isn't finding the char by order, he is finding the minimum index out of all of them so the order doesn't matter.. he stored the indices in the hashmap..

[@mohammadmutawe9783]

public static int firstUniqChar(String str) { HashMap count = new HashMap(); for (char c: str.toCharArray()){ count.put(c, count.getOrDefault(c,0) +1); } for(int i=0;i

[@timurakhalaya6289]

You should try being more efficient , you solutions are far behind.

[@soudiptadutta6886]

Please use Java 9 while coding. If you really help others, you should use the latest version of Java.

[@blasttrash]

what do u mean? what feature of java 9 would be helpful here? thanks

[@CarlosRomero-ef4uv]

Seriously dude? What are you talking about. Not just that but you sound rude, "if you really help others"??? You do realize that when interviewing they, companies, tend to set the version for you. And ill let you know right now, its not the latest. Most importantly , everything you need and are tested for can be solved with earlier versions of java. Its exactly as someone else mentioned. What feature of java 9 would be helpful here? also would you even be allowed to use it? You cant use Arrays.sort(input) if an interview questions is sort this input. I know in real world you would never have to use these but how often would you reverse a string from scratch as well?