Question: Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’.
Answer: Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic.
char returnFirstNonRepeatedChar( char * str )
{
int i, repeated = 0;
int len = strlen(str);
for( i = 0; i < len; i++ )
{
repeated = 0;
for( j = 0; j < len; j++ )
{
if( i != j && str[i] == str[j] ) {
repeated = 1;
break;
}
}
if( repeated == 0 ) { // Found the first non-repeated character
return str[i];
}
}
return '';
}
This approach seems to work perfectly well. But can we do better? Of course we can! With the use of other data structures we can reduce the run time of this algorithm. Any guesses?
A hash table could work really handy here. Although, with this approach, we do sacrifice space for runtime improvement. So we can create a hash table by sequentially reading all the characters in the string and keeping count of the number of times each character appears. Once we’ve created the hash table, we can sequentially read the entries to see which one has a count of one. What is the runtime of this algorithm? We have O(n) to create the hash table and another O(n) to read the entries. This results in a runtime of O(n) + O(n) = O(2n) = O(n).
Have a better solution to this problem? Let us know through the comments section.
Related posts:
progrm to find the first non- repeated element in a string.
A set is not ordered, so you can not keep track of which is first. Here is my implementation using a list. It uses less space than geek’s solution
public static void main(String[] args) {
List seenOnlyOnce = new ArrayList();
List seenTwice = new ArrayList();
for (char c : s) {
if (seenTwice.contains(c))
continue;
if (seenOnlyOnce.contains(c)) {
int idx = seenOnlyOnce.indexOf(c);
seenTwice.add(c);
seenOnlyOnce.remove(idx);
continue;
}
seenOnlyOnce.add(c);
}
System.out.println(“the first unrepeated char is ” + seenOnlyOnce.get(0));
}
2 issues:
1) For the O(n) algorithm, the answer states: “we can sequentially read the entries to see which one has a count of one”. Both the C# and Java implementation of Hashtable will sort your keys so looping through the hashtable’s keys will not give the correct answer. The approach I used was to loop through the characters of the input string (front to back) and pass each character to the hashtable and check for a count of 1. Return the first character that has a count of 1.
2) In response to ck’s comment:
Your algorthm doesn’t work if you have an odd number of repeated characters such as “AAAB”. In this case your algorithm would add A, then remove A, then add A again. It would incorrectly pick up A is the first non-repeated character.
In the first comment by geek, in third step, you need to traverse the original strng, not the array ascii, as you have to find out the first non repeated character in original string.
Solution by ck will not work for the cases a character comes for 3 times.
What about using a set instead of a hashtable ?
Since set’s provide the ability to add an element just once we can use this to remove all repeating chars from the set everytime we find one and then get the first char in the set and return that as the first non repeating char.
Sample Java code:
public static char findFirstNonRepeatedChar(String str) {
Set chSet = new LinkedHashSet();
char[] charArray = str.toCharArray();
for (int i = 0; i < charArray.length; i++) {
if (!chSet.add(charArray[i])) {
chSet.remove(charArray[i]);
}
}
if (chSet.isEmpty())
return '-';
else
return (Character) (chSet.toArray())[0];
}
public static void main(String[] args) {
System.out.println(findFirstNonRepeatedChar("abcdab"));
System.out.println(findFirstNonRepeatedChar("abcdabcd"));
System.out.println(findFirstNonRepeatedChar("abcdabce"));
System.out.println(findFirstNonRepeatedChar("abcdabdce"));
}
1. Use an int array of 256 elements (to accomodate all ascii)
int ascii[256] = 0;
2. For each char in the original string, increment the corresponding ascii element
if we encounter “c”, we set the ascii['c']=ascii['c']++;
3. Traverse the array ascii to get elements with value : 1
Complexity O(n)+ O(256) where n= length of the string