First Non-Repeated Character

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.

If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:

Book Cover
Button

15 Responses

  1. Ashwini says:

    class Program
    {
    static void Main(string[] args)
    {
    string word= “Heey Hyy ded”;
    char[] word_arr = word.ToCharArray();
    int count = 0;
    for (int i = 0; i < word_arr.Length;i++ )
    {
    for(int j=0;j<word_arr.Length;j++)
    {
    if (word_arr[i] == word_arr[j])
    count = count + 1;
    }
    if (count == 1)
    {
    Console.WriteLine("First non – repeative Letter is {0}", word_arr[i]);
    break;
    }
    else
    count = 0;
    }
    Console.WriteLine("No non – repeative Letter ");
    Console.Read();

    }
    }

  2. import java.util.Scanner;
    public class NonrptdChar
    {
    public static void main(String[] args)
    {

    Scanner s=new Scanner(System.in);
    System.out.println(“Enter the String “);
    String str=s.next();
    char[] arr=new char[str.length()];
    for(int j=0;j<arr.length;j++)
    {
    arr[j]=str.charAt(j);
    }
    char found=searchchar(str,arr);
    System.out.println("The first non repeated char is "+found);
    }
    public static char searchchar(String a,char[] b)
    {
    int i=0;
    while(i!=a.length())
    {
    int count=0;
    for(int j=0;j<b.length;j++)
    {
    if(i!=j)
    {
    if(a.charAt(i)!=b[j])
    {
    count++;
    }
    }
    if(count==a.length()-1)
    {
    return a.charAt(i);
    }
    }
    i++;
    }
    return 0;
    }
    }

  3. package mac;
    import java.util.Scanner;
    public class NonrptdChar
    {
    public static void main(String[] args)
    {

    Scanner s=new Scanner(System.in);
    System.out.println(“Enter the String “);
    String str=s.next();
    char[] arr=new char[str.length()];
    for(int j=0;j<arr.length;j++)
    {
    arr[j]=str.charAt(j);
    }
    char found=searchchar(str,arr);
    System.out.println("The first non repeated char is "+found);
    }
    public static char searchchar(String a,char[] b)
    {
    int i=0;
    while(i!=a.length())
    {
    int count=0;
    for(int j=0;j<b.length;j++)
    {
    if(i!=j)
    {
    if(a.charAt(i)!=b[j])
    {
    count++;
    }
    }
    if(count==a.length()-1)
    {
    return a.charAt(i);
    }
    }
    i++;
    }
    return 0;
    }
    }

  4. sanjay says:

    1] Take a Dictionary
    2] if key is already present make value -1,
    Don’t Do anything if key is present and value is -1.
    if key is not present put the sequence number of key.
    3] one completion of string traverser the dictionary with lowest key (and not equal to -1) is the 1st non-repetear

  5. k jain says:

    After creating the hash table,
    look for the count of each character in the hash, with the same sequence as it is in the string. Return the one that has hash value ==1. this will give you the first non repeating char in O(n).

  6. MJ says:

    private static Character nonRepeatedChar(String str) {
    // TODO Auto-generated method stub
    int[] ch=new int[256];
    for(int i=0;i<ch.length;i++){
    ch[i]=0;
    }
    for(int i=0;i<str.length();i++){
    ch[str.charAt(i)]++;
    }
    for(int i=0;i<str.length();i++){
    if(ch[str.charAt(i)]==1){
    return str.charAt(i);
    }
    }
    return null;
    }

  7. My Solution in Java:

    import java.util.HashSet;

    public class Trie {

    public Character getFirstUnique(String data) {
    Character retc = null;
    if (data != null) {

    HashSet unique = new HashSet();
    HashSet repeated = new HashSet();
    for (int i = 0; i 1) {
    for (int i = 0; i < data.length(); i++) {
    if (unique.contains(data.charAt(i))) {
    retc = data.charAt(i);
    break;
    }
    }
    } else if (unique.size()==1){
    retc = (Character)unique.toArray()[0];
    }

    }
    return retc;
    }

    public static void main(String args[]) {
    Trie t = new Trie();
    System.out.println(t.getFirstUnique("abcdab"));
    }
    }

  8. balaji says:

    straight forward approach
    public string FirstNonRepeativeChar(string RepeatedChar)
    {
    string NonRepeated = string.Empty;
    foreach (char str1 in RepeatedChar.ToString())
    {
    int count = 0;
    foreach (char str2 in RepeatedChar.ToString())
    {
    if (str1 == str2)
    count += 1;
    }
    if (count == 1)
    {
    NonRepeated = str1.ToString() ;
    break;
    }
    }
    return NonRepeated;
    }

  9. AlgoGeek says:

    @ck: how does it work for 3 repeating characters in string? eg: “aaab” will report ‘a’ as non-repeating character. You will need Amit’s logic and use two LinkedHashSets. Using LHS will give constant time advantage over using ArrayList.

  10. himanshu says:

    progrm to find the first non- repeated element in a string.

  11. Amir says:

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

  12. Dave F says:

    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.

  13. Vineet says:

    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.

  14. ck says:

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

  15. geek says:

    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

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>