Find the first non-repeating character in a string

Question

Martin · Accepted Answer

The straightforward answer is to loop over the string, and for each character check the whole string if it is repeated.
This solution is O(n^2).

Better would be to remember each character visited and keep a count of how often it was encountered. You would initially have a 0 count for every character in the alphabet, or an empty hash map with the same purpose. Then go over the whole string and increment the counter for each character you encounter.
Finally, go over the string and look up for each character how often it was encountered. The first one with a count of 1 is the one you are looking for.

This algorithm requires the list to be searched twice, and is O(n).

srinivas reddy · Answer

This following code should work for finding first unrepeatable char in string

public static char checkFirstUnRepeatableChar(String text){
		
	    BitSet set = new BitSet(256);
	    BitSet repeated = new BitSet(256);
	    
        for (char ch : text.toCharArray()) {
        	
			if (!set.get((int) ch)) {
				set.set((int) ch);
			} else {
				repeated.set((int) ch);
			}
            
        }
        
        for(char ch : text.toCharArray()){
        if( !repeated.get((int)ch))
          return ch;	
        	
        }
        
        return 0;
		
		
	}

rach · Answer

According to me, one can better create a hash table with each alphabet as  a key of the string and then use chaining for recurrence of the alphabets.... Now simply apply searching algo to find first alphabet with zero repetition...

Sigiloso · Answer

In Java, better than O(n), ie returns in < 256 checks. Small RAM footprint since it uses one Byte (the BitSet instance) to track characters.

public char check(String text) {
        BitSet set = new BitSet(256);
        
        for (char ch : text.toCharArray()) {
            if (!set.get((int)ch)) {
                set.set((int)ch);
            } else {
                return ch;
            }
        }
        return 0;
    }

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas