1. Introduction

In this article we will see how to search for first non-repeating character in the word.

2. Different ways to search for first non-repeating character

Let us consider the word
    Example: java
    Output: j
    Example mississippi
    Output m

We will discuss few ways to do so with time and space trade offs.

3. Using LinkedHashMap

We can use LinkedHashMap<K, V> and insert K as character and V as count of characters, where K is key i.e. character and V is value i.e. count of that character. Good thing about LinkedHashMap<K, V> is that it maintains the order of insertion. Now we can iterate through the Map and get the K whose V is 1.

/**
 * In this method we use LinkedHashMap which maintains the insertion 
 * order.
 */
public static 
Optional<Character> firstNonRepeatingByLinkHashMap(String str) {

    Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();

    char[] ch = str.toCharArray();
    /**
     * process the char[] ch place each character in map. if the
     * character is repeated then get old value and add 1 to it. 
     * else the character is new then insert 1 as value
     */
    for (int i = 0; i < ch.length; i++) {
        if (map.containsKey(ch[i])) {
            map.put(Character.valueOf(ch[i]), map.get(ch[i]) + 1);
        } else {
            map.put(Character.valueOf(ch[i]), 1);
        }
    }

    Set<Entry<Character, Integer>> entries = map.entrySet();
    for (Entry<Character, Integer> entry : entries) {
        if (entry.getValue() == 1) {
            return Optional.of(entry.getKey());
        }
     }

    return Optional.empty();
}

Assert.assertEquals(
			Optional.of(Character.valueOf('a')), 
			firstNonRepeatingByLinkHashMap("a"));

4. Using HashMap

HashMap<> does not insert the data into Map in ordered way. But nevertheless we can use it for this problem. Iterate through the String and insert K as character and V as count of characters. Now again iterate through the String and check for every character is corresponding V is 1.

/**
 * In this method we use HashMap. Remember HashMap does 
 * not maintain insertion ordered as it is unordered collection.
 */
public static 
Optional<Character> firstNonRepeatingByHashMap(String str) {

    Map<Character, Integer> map = new HashMap<Character, Integer>();
    char[] ch = str.toCharArray();
    for (int i = 0; i < ch.length; i++) {
        if (map.containsKey(ch[i])) {
            map.put(Character.valueOf(ch[i]), map.get(ch[i]) + 1);
        } else {
            map.put(Character.valueOf(ch[i]), 1);
         }
    }

    for (char chr : str.toCharArray()) {
        if (map.get(chr) == 1) {
            return Optional.of(Character.valueOf(chr));
        }
    }

    return Optional.empty();
}

Assert.assertEquals(
			Optional.of(Character.valueOf('m')), 
			firstNonRepeatingByHashMap("missisipi"));

5. Using Array

Use an int[] of 256. Loop through all the characters of the String and store the count of character in character’s index i.e. chars[str.charAt(i)]. Now just search for the count at character’s index and check if it is 1, if yes we found the character.

/**
 * This method uses an array of 256 to mark entry o character.
 */
public static 
Optional<Character> firstNonRepeatingCharacterByArray(String str) {

    int[] chars = new int[256];
    for (int i = 0; i < str.length(); i++) {
        chars[str.charAt(i)]++;
    }

    for (char ch : str.toCharArray()) {
        if (chars[ch] == 1) {
            return Optional.of(Character.valueOf(ch));
         }
     }

    return Optional.empty();
}

Assert.assertEquals(
			Optional.of(Character.valueOf('b')), 
			firstNonRepeatingCharacterByArray("aab"));

Assert.assertEquals(
			Optional.empty(), 
			firstNonRepeatingCharacterByArray(""));

All of the above solutions has time complexity of O(n) and space complexity of O(n).

Time Complexity is O(n) because we traverse entire string.

Space Complexity is O(n) because we are using additional space to process the String.

6. Conclusion

In this article, we learned how to search for first non-repeating character in a word using LinkedHashMap, HashMap and an array.