Dada una cadena, ¿encuentra la longitud de la subcadena más larga donde ningún personaje se repite dos veces?

Pregunta de entrevista famosa de hoy en día. Aquí está el algoritmo

Método 1: Algoritmo ingenuo
Verifique si cada subcadena tiene caracteres repetidos. De lo contrario, verifique si es la subcadena más larga o no.
Complejidad del tiempo: O (n ^ 3)
Complejidad espacial: O (1)

Método 2: Algoritmo de tiempo lineal
1. Cree una matriz charIndexes que tenga el último índice de caracteres de cadena visto en la cadena, inicializado a -1
2. Atraviese la matriz y compruebe si el carácter actual se vio anteriormente en la submatriz actual, si no se ve, incremente el índice de la subcadena no repetida actual vista hasta ahora (currLength).
3. Si el carácter actual es un carácter repetido y la longitud de la subcadena más larga (maxLength) vista hasta ahora es menor que la longitud actual, actualice maxLength.
Complejidad del tiempo: O (n)
Complejidad espacial: O (1)

• ¿Puedo usar el enfoque de fuerza bruta para resolver preguntas de algoritmos en la entrevista técnica?
• ¿Cuál es la mejor manera de prepararse mental y físicamente para absorber tanta información sobre un tema técnico como sea posible en una semana?
• ¿Qué tipo de preguntas se le pueden hacer a un chico de CS en una entrevista de Power Grid (PSU) para una publicación de ingeniero (IT)?
• ¿Cuánto importa la velocidad en la programación de entrevistas y hay escenarios en los que la velocidad es más importante que en otros?
• Dada una matriz entera y un número constante X, imprima todos los pares de números en la matriz cuyo producto es igual a X. Seguimiento: ¿cómo lo hará en O (n)? ¿Cómo manejarás los pares duplicados?

clase pública LongestSubstring {

// Algoritmo ingenuo para encontrar la subcadena más larga sin repetir caracteres
// Complejidad cuadrática del tiempo
Cadena estática pública getLongestSubstringNonRepeatingCharsNaive (String str) {
String longestSubstring = “”;
for (int i = 0; i <str.length (); i ++) {
for (int j = i; j <str.length (); j ++) {
if (hasRepeatingChars (str, i, j)) {
rotura;
} else if (longestSubstring.length () <j-i + 1) {
longgestSubstring = str.substring (i, j + 1);
}
}
}
volver más larga
}

private static boolean hasRepeatingChars (String str, int start, int end) {
boolean [] isCharPresent = new boolean [256];
para (int i = 0; i <256; i ++) {
isCharPresent [i] = falso;
}
for (int i = start; i <= end; i ++) {
if (isCharPresent [str.charAt (i)]) {
volver verdadero;
} más {
isCharPresent [str.charAt (i)] = verdadero;
}
}
falso retorno;
}

// Algoritmo de tiempo lineal para encontrar la subcadena más larga sin repetir caracteres
Cadena estática pública getLongestSubstringNonRepeatingChars (String str) {

if (str == null) {
volver nulo;
}

int n = str.length ();
si (n <2) {
volver str;
}

// matriz para almacenar el último índice de caracteres de cadena visto en la cadena, inicializado a -1
int [] charIndexes = new int [256];
para (int i = 0; i <n; i ++) {
charIndexes [i] = -1;
}

// Establecer índice del primer carácter
charIndexes [str.charAt (0)] = 0;

int currLength = 1; // Longitud de la subcadena actual no repetida
int maxLength = 1; // Longitud de la subcadena más larga con caracteres no repetidos encontrados
int prevIdx = 0; // índice anterior del personaje actual
int startIdx = 0; // Índice inicial de la subcadena más larga con caracteres no repetidos encontrados

para (int i = 1; i <n; i ++) {
prevIdx = charIndexes [str.charAt (i)];
if (prevIdx == -1 || i – currLength> prevIdx) {
currLength ++;
} más {
if (currLength> maxLength) {
maxLength = currLength;
startIdx = i – maxLength;
}
currLength = i – prevIdx;
}
charIndexes [str.charAt (i)] = i;
}

// Comprueba si la subcadena más larga con caracteres no repetidos termina al final de la cadena
if (currLength> maxLength) {
maxLength = currLength;
startIdx = n – maxLength;
}

return str.substring (startIdx, startIdx + maxLength);
}

public static void main (String [] args) {
String str = “ABCDABDEFGCABD”;
/ * String longestSubstring = getLongestSubstringNonRepeatingCharsNaive (str);
System.out.println (“Caracteres no repetidos de subcadena más largos por método Naive: \ t \ t” + longestSubstring); * /
String longestSubstring = getLongestSubstringNonRepeatingChars (str);
System.out.println (“Caracteres no repetitivos de subcadena más largos por método de tiempo lineal: \ t” + más largoString)

}
}

Créditos: la subcadena más larga con caracteres no repetidos
Verifique la visualización del algoritmo en la página web, es genial ver que el algoritmo se ejecuta y se anima sobre la marcha.