Cómo encontrar la subcadena más larga de caracteres únicos de una cadena usando Java

05/08/2019

Esta es una pregunta de una entrevista en Google: una secuencia de caracteres se detiene, encuentra la subcadena más larga de caracteres únicos en esa secuencia. El flujo puede ser asimilado a una matriz de caracteres.

Este problema se resuelve utilizando una ventana deslizante en los caracteres de entrada y manteniendo un índice con el número de veces que se encuentra un carácter en la ventana actual. Para todos los caracteres de la entrada, la posición de la ventana final se incrementa en uno y el carácter actual se agrega al índice. Hasta que la ventana tenga el tamaño esperado, eliminamos un carácter desde el principio de la ventana. Si la ventana actual es más larga que el máximo actual, la guardamos. Al final del proceso, devolvemos la ventana máxima.

Crea el siguiente archivo 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( );
	}
    }    
}

El resultado será:

input = aabacbebebe
k = 1
output = aa

k = 2
output = bebebe

k = 3
output = cbebebe

k = 4
output = aabacbebebe

Si es necesario devolver todas las ventanas más largas, debemos mantener una lista de las ventanas que coincidan con la longitud máxima.

Pregunta de entrevista de Google

Referencias

Java HashMap