Given a stream of characters, find the first non-repeating i.e. unique character occurred.

For example, in a stream [a,c,b,a,d,a,…] first unique is ‘c’ but if another ‘c’ character comes to stream [a,c,b,a,d,a c,…] then first unique would be ‘b’.

We need some data structure that can maintain the order of each character appearing first time in the string. We can use Linkedhashset for this purpose. Below is an implementation of finding first unique using LinkedHashset. Note that w also need a hashset to track which element repeated. This is O(n) time and O(n) space solution.

public static char firstUnique(char[] stream){
	HashSet<Character> seen = new HashSet<Character>();
	LinkedHashSet<Character> uniques = new LinkedHashSet<Character>();
	
	for(int i = 0; i < stream.length; i++){
		char c = Character.toLowerCase(stream[i]);
		if(!seen.contains(c)){
			seen.add(c);
			uniques.add(c);
		}
		else{
			uniques.remove(c);
		}
	}
	
	if(uniques.size() > 0){
		return uniques.iterator().next();
	}
	else return '\0';
}