First Non-Repeating Character

Problem Statement

Given an input string, find the first non-repeating character in it.

Solution

Let us take an example string like “aabccdeff“. The question is asking us to return the first character that does not repeat. In this case the first non-repeating character is “b“

Approach

1. Declare a hashmap with Character as key and Boolean as value.
2. Iterate the string with a simple for loop and push the characters in this hashmap
3. While inserting the character, check if it already exists in the hashmap. If it does, then insert with value as false else insert with value as true.
4. Now iterate the string again and check the status of each character against the hashmap. The first character we notice with value as true is our answer.

Note That:

1. The number of entries in the hashmap is the number of distinct characters in the string.
2. The first time a character is inserted in the hashmap, it is inserted with value as true. If the same character is seen again then its corresponding value in the hashmap is changed to false.
3. Now we know that every character in the hashmap with value as false is repeating character. We are interested in the first character with value as true in hashmap which we can easily find in second iteration.
4. Thus, we are able to solve this problem in O(n) complexity.

Example Code

Let us write a Java class for this:

public class Sample {

public static void main(String[] args) {
  
    String str = "aabccdeff";
    Map<Character, Boolean> charCountMap = new  HashMap<Character, Boolean>();

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

        char c = str.charAt(i);

        if(charCountMap.containsKey(c)) {

            charCountMap.put(c, false);        
        } // endIf
        else {

            charCountMap.put(c, true);         
        }

    } // endFor

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

        char c = str.charAt(i);
        boolean bool = (boolean) charCountMap.get(c);

        if(bool) {

            System.out.println("first non-repeating character is: " + c);
            break;
        } // endIf

    } // endFor
 }
}

This code returns the following output:

first non-repeating character is: b