LeetCode – Subsecuencia de ventana mínima (Java)

Dadas las cadenas S y T, encuentre la subcadena mínima (contigua) W de S, de modo que T sea una subsecuencia de W.

Si no existe tal ventana en S que cubra todos los caracteres en T, devuelve la cadena vacía «». Si hay varias de estas ventanas de longitud mínima, devuelva la que tiene el índice de inicio más a la izquierda.

Ejemplo 1:

Aporte:
S = «abcdebdde», T = «bde»
Salida: «bcde»
Explicación:
«bcde» es la respuesta porque aparece antes de «bdde», que tiene la misma longitud.
«deb» no es una ventana más pequeña porque los elementos de T en la ventana deben aparecer en orden.

Solución 1 de Java: dos punteros

De una manera de fuerza bruta, este problema se puede resolver usando dos punteros que iteran sobre los caracteres de las dos cadenas respectivamente.

public String minWindow(String S, String T) {
    int start=0;
    String result = "";
 
    while(start<S.length()){
        int j=0;
 
        for(int i=start; i<S.length(); i++){
            if(S.charAt(i)==T.charAt(j)&&j==0){
                start=i;
            }
 
            if(S.charAt(i)==T.charAt(j)){
                j++;
            }
 
            if(j==T.length()){
                if(result.equals("")||(i-start+1)<result.length()){
                    result = S.substring(start, i+1);
                }
                start=start+1;
                break;
            }
 
            if(i==S.length()-1){
                return result;
            }
        }
    }
 
    return result;
}