Como encontrar a subseqüência mais longa de caracteres únicos de uma String usando Java

05/08/2019

Esta é uma pergunta de uma entrevista no Google: um fluxo de paradas de caracteres, encontrar a substring mais longa de caracteres únicos nesse fluxo. O fluxo pode ser assimilado a uma matriz de caracteres.

Esse problema é resolvido usando uma janela deslizante nos caracteres de entrada e mantendo um índice com o número de tempo que um caractere é encontrado na janela atual. Para todos os caracteres da entrada, a posição da janela final é aumentada em um e o caractere atual é adicionado ao índice. Até que a janela seja o tamanho esperado, removemos o caractere desde o início da janela. Se a janela atual for maior que o máximo atual, nós a salvamos. No final do processo, retornamos a janela máxima.

Crie o seguinte arquivo java:

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( );
	}
    }    
}

O resultado será:

input = aabacbebebe
k = 1
output = aa

k = 2
output = bebebe

k = 3
output = cbebebe

k = 4
output = aabacbebebe

Se todas as janelas mais longas precisarem ser retornadas, precisamos manter uma lista das janelas que correspondam ao comprimento máximo.

Pergunta da entrevista do Google

Referências:

Java HashMap