Find First Unique Character in a String

Problem

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Examples

Example 1:

Input:
s = "leetcode"
Output:
 0

Example 2:

Input:
s = "loveleetcode"
Output:
 2

Example 3:

Input:
s = "aabb"
Output:
 -1

Example

String input = " tutorial horizon"
Output: 'u'
String input = "aabbccadd"
Output: No non-repeating character found.

Similar but more interesting problem - First Unique Character in a Stream of Characters

Solution

Method 1 - Brute Force

This problem can be easily solved using two nested loops. Take each character from the outer loop and check the character in rest of the string using inner loop and check if that character appears again, if yes then continue else return that character.  Time complexity is O(N^2).

Method 2 - Two Pass - Use Hashset/HashMap/Array Indices

Here is what we can do:

  1. Scan the string from left to right and construct the count array or hashmap.
  2. Again, scan the string from left to right and check for count of each character, if you find an element who’s count is 1, return it.

Using Count or Freq Array

Here is how to use count array:

Input string: str = geeksforgeeks
1: Construct character count array from the input string.
 ....
 count['e'] = 4
 count['f'] = 1
 count['g'] = 2
 count['k'] = 2
 ……
2: Get the first character who's count is 1 ('f').
Code
Java
public int firstUniqChar(String s) {
	int freq [] = new int[26];
	for(int i = 0; i < s.length(); i ++)
		freq [s.charAt(i) - 'a'] ++;
	for(int i = 0; i < s.length(); i ++)
		if(freq [s.charAt(i) - 'a'] == 1)
			return i;
	return -1;
}

Using Hashmap

Code
Java
public int firstUniqChar(String s) {
	if(s==null || s.length()==0)
		return -1;
	Map<Character, Integer> charToC = new HashMap();
	for(char ch : s.toCharArray()) {
		charToC.put(ch, charToC.getOrDefault(ch, 0)+1);
	}
	for(int i=0; i<s.length(); i++){
		if(charToC.get(s.charAt(i)) ==1){
			return i;
		}
	}
	return -1;
}

Time complexity: O(N) Space Complexity: O(N)

Method 3 - Using LinkedHashmap and Set with One Pass 🏆

public int firstUniqChar(String s) {
	Map<Character, Integer> map = new LinkedHashMap<>();
	Set<Character> set = new HashSet<>();
	for (int i = 0; i < s.length(); i++) {
		if (set.contains(s.charAt(i))) {
			//just removing key, even if it doesn't exists
			// as java doesnt throw exception
			map.remove(s.charAt(i));
			
		} else {
			map.put(s.charAt(i), i);
			set.add(s.charAt(i));
		}
	}
	return map.size() == 0 ? -1 : map.entrySet().iterator().next().getValue();
}

Time complexity: O(N) Space Complexity: O(N)

Method 4 - Traversing String Only Once Storing char’s First Index

The above approach takes O(n) time, but in practice it can be improved. The first part of the algorithm runs through the string to construct the count array (in O(n) time). This is reasonable. But the second part about running through the string again just to find the first non-repeater is not good in practice. In real situations, your string is expected to be much larger than your alphabet. Take DNA sequences for example: they could be millions of letters long with an alphabet of just 4 letters. What happens if the non-repeater is at the end of the string? Then we would have to scan for a long time (again).

We can augment the count array by storing not just counts but also the index of the first time you encountered the character e.g. (3, 26) for ‘a’ meaning that ‘a’ got counted 3 times and the first time it was seen is at position 26. So when it comes to finding the first non-repeater, we just have to scan the count array, instead of the string

Here is the CountIndex: 

class CountIndex {
	int count, index;

	// constructor for first occurrence
	public CountIndex(int index) {
		this.count = 1;
		this.index = index;
	}

	// method for updating count
	public void incCount() {
		this.count++;
	}
}

Here is the actual algorithm:

static final int NUM_CHARS = 256;

/* calculate count of characters
 in the passed string */
static HashMap<Character, CountIndex> getCharCountArray(String str) {
	HashMap<Character, CountIndex> hm = new HashMap<Character, CountIndex> (NUM_CHARS);

	for (int i = 0; i<str.length(); i++) {
		if (hm.containsKey(str.charAt(i))) {
			hm.get(str.charAt(i)).incCount();
		} else {
			hm.put(str.charAt(i), new CountIndex(i));
		}

	}
	return hm;
}

/* The method returns index of first non-repeating
 character in a string. If all characters are repeating
 then returns -1 */
static int firstNonRepeating(String str) {
	HashMap<Character, CountIndex> hm = getCharCountArray(str);
	int result = Integer.MAX_VALUE;

	for (Character c: hm.keySet()) {
		CountIndex ci = hm.get(c);
		// If this character occurs only once and appears
		// before the current result, then update the result
		if (ci.count == 1 && result > ci.index) {
			result = ci.index;
		}

	}

	return result;
}

Time complexity - O(n) + O(256) = O(n) Space complexity - O(n)

Method 5 - Using lastIndexOf

public int firstUniqChar(String s) {
	for(char c : s.toCharArray()){
		int index = s.indexOf(c);
		int lastIndex = s.lastIndexOf(c);
		if(index == lastIndex)
			return index;
	}
	return -1;
}

Time complexity - O(n^2)