Encuentre la subcadena más larga sin caracteres repetidos

Programación

1. Información general

En este tutorial, compare formas de encontrar la subcadena más larga de letras únicas utilizando Java. Por ejemplo, la subcadena más larga de letras únicas en "CODINGISAWESOME" es "NGISAWE".

2. Enfoque de fuerza bruta

Comencemos con un enfoque ingenuo. Para empezar, podemos examinar cada subcadena si contiene caracteres únicos:

String getUniqueCharacterSubstringBruteForce(String input) { String output = ""; for (int start = 0; start < input.length(); start++) { Set visited = new HashSet(); int end = start; for (; end < input.length(); end++) { char currChar = input.charAt(end); if (visited.contains(currChar)) { break; } else { visited.add(currChar); } } if (output.length() < end - start + 1) { output = input.substring(start, end); } } return output; }

Dado que hay n * (n + 1) / 2 posibles subcadenas, la complejidad de tiempo de este enfoque es O (n ^ 2) .

3. Enfoque optimizado

Ahora, echemos un vistazo a un enfoque optimizado. Comenzamos a atravesar la cuerda de izquierda a derecha y mantenemos un seguimiento de:

  1. la subcadena actual con caracteres no repetidos con la ayuda de un índice inicial y final
  2. la salida de subcadena no repetida más larga
  3. una tabla de búsqueda de personajes ya visitados
String getUniqueCharacterSubstring(String input) { Map visited = new HashMap(); String output = ""; for (int start = 0, end = 0; end < input.length(); end++) { char currChar = input.charAt(end); if (visited.containsKey(currChar)) { start = Math.max(visited.get(currChar)+1, start); } if (output.length() < end - start + 1) { output = input.substring(start, end + 1); } visited.put(currChar, end); } return output; }

Para cada personaje nuevo, lo buscamos en los personajes ya visitados. Si el carácter ya ha sido visitado y es parte de la subcadena actual con caracteres no repetidos, actualizamos el índice de inicio. De lo contrario, continuaremos atravesando la cadena.

Dado que estamos atravesando la cadena solo una vez, la complejidad del tiempo será lineal u O (n) .

Este enfoque también se conoce como patrón de ventana deslizante.

4. Prueba

Finalmente, probemos a fondo nuestra implementación para asegurarnos de que funciona:

@Test void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected() {  assertEquals("", getUniqueCharacterSubstring(""));   assertEquals("A", getUniqueCharacterSubstring("A")); assertEquals("ABCDEF", getUniqueCharacterSubstring("AABCDEF")); assertEquals("ABCDEF", getUniqueCharacterSubstring("ABCDEFF")); assertEquals("NGISAWE", getUniqueCharacterSubstring("CODINGISAWESOME")); assertEquals("be coding", getUniqueCharacterSubstring("always be coding")); }

Aquí, probamos y probamos las condiciones de contorno, así como los casos de uso más típicos .

5. Conclusión

En este tutorial, hemos aprendido cómo usar la técnica de la ventana deslizante para encontrar la subcadena más larga con caracteres no repetidos.

Y, como siempre, el código fuente está disponible en GitHub.