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:
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
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"));
}