# Programming Interview Questions 15: First Non Repeated Character in String

One of the most common string interview questions: Find the first non-repeated (unique) character in a given string.

This question demonstrates efficient use of hashtable. We scan the string from left to right counting the number occurrences of each character in a hashtable. Then we perform a second pass and check the counts of every character. Whenever we hit a count of 1 we return that character, that’s the first unique letter. If we can’t find any unique characters, then we don’t return anything (None in python). Here’s the code:

```def firstUnique(text): counts=collections.defaultdict(int) for letter in text: counts[letter]+=1 for letter in text: if counts[letter]==1: return letter```

As you can see it’s pretty straightforward once we use a hashtable. It’s an optimal solution, the complexity is O(N). Hashtable is generally the key data structure to achieve optimal linear time solutions in questions that involve counting.

VN:F [1.9.22_1171]
Programming Interview Questions 15: First Non Repeated Character in String, 7.5 out of 10 based on 15 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
• http://ahmetalpbalkan.com alp

I think we can traverse the string only once by keeping two trees, one is just a binary search tree to keep nodes of characters and their counts, one is a minheap to keep those nodes sorted and while traversing we’ll maintain the heap and then after the traversal is finished, answer is at the root of the heap. That comes with a memory paste and we can maintain the heap in O(N) time, I think. That’s not a better solution, just wanted to leave it here.

• Arden

Good alternative solution. But if we replace the binary search tree with hashtable, updating the counts will be slightly faster I guess?

• Kowshik

Heres a twist to the same problem that I encountered in one of my recent interviews. What if the given string is extremely huge and the character set is lowercase letters (‘a’ to ‘z’)?

Answer: Firstly, we can replace the hash table with an array of pairs of size 26 (each representing a lowercase letter):
– The first element in each pair stores the location where the character occured for the first time in the string (default value is -1 indicating non-occurence).
– The second element in each pair is a boolean that indicates if the character’s occurence is unique. (default value is false and it also indicates repetition. true indicates uniqueness.)

With this data structure ready, it is enough if we parse through the original string only once to populate the array of pairs. Then we do a scan on the array to figure out the first unique character.

• Arden

You’re totally right. I have a post ready to publish discussing exactly this solution. It’ll be number 25: remove duplicate characters in string. Thanks for the comment..

• Kowshik

An optimization which a friend of mine pointed out to me: Instead of an array of pairs, we can use just use an array of integers, where -1 (default value) represents non-occurence of the character and -2 represents duplication.

• Vikram N

Good one!

• http://colesherer.com Cole Sherer

If you scan right to left in your original solution, you can keep track of the most recent key that was not already in the hashtable. Once you traverse the string once, this will be set to the leftmost (first) non-repeated character.

• Xiaohui Liu

What if you find a key that is the most recent key that is not in the hash table till now, when scanning from right to left? For instance, 1, 1, 2. How would your solution work?

• Sri

Would like to post Java implementation of the same solution

public class App {

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println(firstNonRepeatedCharacter(“abbbccdea”));

}

// O(n solution)

public static char firstNonRepeatedCharacter(String str){

for(int i =0;i<str.length();i++){

if(count.containsKey(str.charAt(i)))

count.put(str.charAt(i), count.get(str.charAt(i))+ 1);

else

count.put(str.charAt(i), 1);

}

for(Character input : count.keySet()){

if(count.get(input) == 1)

return input;

}

return ' ';

}

}

• Vikram N

@Sri,

I think, the code you have posted is incomplete.

• qwert_buddy

I think this is very Python specific. In Java, you cannot iterate on a fixed order over a HashMap. So I think a HashMap would not work if you try to do this in java?

• qwert_buddy

Got it. Iterating over the string again the same order would work.

• baris evrim demiroz

You can always use LinkedHashMap for predictable iteration order.

• Victor

You dont have to iterate over the hashMap, if you re-iterate through the input string and do the hash look up, it is guaranteed the same order.

• Gallon

It can be resolved in one iteration with double linked list + hashtable.

Go through each character in the string (or stream),
(a). if the character is NOT in hashtable, create a node with value of character and append it to double linked list, insert node address into hashtable, hash key is character itself.
(b). Else If the character is already in hashtable, we know it’s NOT a unique character any more. Find the address of orresponding node via hashtable and delete it from double linked list. No need to remove the character from hashtable.

1st node in the double linked list is always 1st non-repeat character in the string.

• Kamal Chaya

Is it valid to use set?

Why can’t we xor all elements ?

>>> s = “abcab”

>>> d = 0

>>> for x in s:

… d = d ^ ord(x)

>>> d

99

• Architect

``` //Java 8 Streams & Lambdas solution by the Architect https://disqus.com/by/op8rv315/ String text = "One of the most common string interview questions".toLowerCase();```

``` OptionalInt firstunique = IntStream.range(0, text.length()) .filter(s -> !text.substring(0, s).contains(text.substring(s, s+1)) && !text.substring(s+1, text.length()).contains(text.substring(s, s+1))) .findFirst(); ```

```System.out.println(text.substring(firstunique.getAsInt(), firstunique.getAsInt()+1)); ```