How to find the longest substring of unique characters from a String in Java

05/08/2019

This is a question from an interview at Google: a Stream of character stops, find the longest substring of unique characters in that Stream. The stream can be assimilated to an array of characters.

This problem is solved by using a sliding window on the input characters and maintaining an index with the number of time a character is found in the current window. For all the characters of the input, the end window position is increased by one and the current character is added to the index. Until the window is the expected size, we remove the a character from the beggining of the window. If the current window is longer that the current maximum, we save it. At the end of the process, we return the maximum window.

Create the following java file:

import java.util.HashMap;
import java.util.Map;

public class InterviewLongestSubString {

    protected void addCharIndex( Map<Character, Integer<g index, char in ){
	if( !index.containsKey( in ) ){
	    index.put(in, 1);
	    return;
	}
	
	// Increment and add
	index.put(in, index.get(in)+1);
    }

    protected void removeCharIndex( Map<Character, Integer> index, char in ){
	if( !index.containsKey( in ) ){
	    return;
	}
	
	int currentValue = index.get(in);
	if( currentValue == 1 ){
	    index.remove( in );
	    return;
	}
	
	// Decrement the value
	index.put(in, currentValue-1);
    }
    
    protected boolean isValidWindow(Map<Character, Integer> index, int size){
	if( index.keySet().size() > size )
	    return false;
	
	return true;
    }
    
    public String process(String in, int k){
	Map<Character, Integer> index = new HashMap<Character, Integer>();
		
	char[] tab = in.toCharArray();
	int currentWindowStart = 0, currentWindowEnd = 0; 
	int maxWindowStart = 0, maxWindowSize = 0; 
	
	// Loop on all the chars
	for(int i=0 ; i < tab.length ; i++){
	    char c = tab[i];
	    
	    addCharIndex(index, c);
	    
	    currentWindowEnd++;
	    
	    while( !isValidWindow(index,k) ){
		removeCharIndex(index, tab[currentWindowStart] );
		currentWindowStart++;
	    }
	    
	    int currentWindowSize = currentWindowEnd - currentWindowStart + 1;
	    if( currentWindowSize > maxWindowSize ){
		maxWindowSize = currentWindowSize;
		maxWindowStart = currentWindowStart;
	    }
	}
	
	// return the String found
	return in.substring(maxWindowStart,maxWindowStart+maxWindowSize-1 );
    }
    
    public static void main(String[] argv){
	InterviewLongestSubString o = new InterviewLongestSubString();
	
	String s = "aabacbebebe"; 
	System.out.println( "input = " + s );
	for(int i = 1; i < 5; i++){
	    System.out.println( "k = " + i );
	    System.out.println( "output = " + o.process(s, i) );
	    System.out.println( );
	}
    }    
}

The output will be:

input = aabacbebebe
k = 1
output = aa

k = 2
output = bebebe

k = 3
output = cbebebe

k = 4
output = aabacbebebe

If all the longest windows need to be returned, we need to maintain a list of the windows that match the maximum length.

Google interview question

References:

Java HashMap