Selecting the first non-repeating character

Question: Write a function that finds the first non-repeated character in a String.

Related Tags:

Questions

  1. Does casing matter?

Casing should usually matter, as this problem looks at chars, and not just letters. However, it doesn't hurt to clarify.

Algorithm

Our algorithm can be broken up into two steps:

  1. Store each char as a Character object in a HashMap, mapping its value to the number of times it appears in the string.
  2. Iterate through the HashMap, in order of each Character's appearance, until we find a Character where the number of times it appeared was only once.

This is a O(2n) time algorithm, since we are iterating through the list twice.

Implementation in Java

Here is an implementation in Java.

static Character findFirstNoRepeatChar(String s) {
	HashMap<Character, Integer> charHash = new HashMap<>();

	Character c;

	// Iterate through the list and for each Character place into our HashMap.
	for (int i = 0; i < s.length(); i++) {
		c = s.charAt(i);
		// If c is already stored, increment
		if (charHash.containsKey(c)) {
			charHash.put(c, charHash.get(c)+1);
		// Else, set value of 1
		} else {
			charHash.put(c, 1);
		}
	}

	// Now iterate through the list and return the first c == 1
	for (int i = 0; i < s.length(); i++) {
		c = s.charAt(i);

		if (charHash.get(c) == 1) {
			return c;
		}
	}

	return null;
}

Came up with a better solution or have a question? Comment below!