Question: Given a string,find the first un-repeated character in it.
SOlution 1:
In case the string is a valid string. It has only characters a to z then we can create an array of size 26. Initialize each element in the array to 0 and then once u find a character go to that index and increment the value of array[character - 'a']
Scan again the original array and check the value of array[index-'a'] if the value is not set then it is the first un-repeated character.
Subscribe to:
Post Comments (Atom)
Hey man... ur blog showed up in Google search!!
ReplyDeleteI had to do this one for a job screening, in fact I had to do several.
ReplyDeletehttp://www.cloud-it.com/challenge/
You can review my solutions, its along your lines, but more flexible and well annotated.
your Soln needs 2 scans of input string and memory for 26 characters and counter and comparisons.
ReplyDeleteOne optimized way is to maintain 2 linked lists(unique and nonUnique)
scan through the string Get chars one by one
Append to the unique list if char not present in nonunique list and unique list.
Else if present in uniquelist remove the char and add it in nonunique list.
At the end of scan take the char in the head of the unique list .
regards
Ansil
Ansilf.spaces.live.com
public Character findFirstRepeatedCharacter(String s){
ReplyDeletechar[] charArr = s.toCharArray();
HashSet set = new HashSet();
for(char c: charArr) {
if(set.contains(c)) {
return c;
}
else {
set.add(c);
}
}
return null;
}