Trova la sottostringa più lunga senza ripetere i caratteri

1. Panoramica

In questo tutorial, confronta i modi per trovare la sottostringa più lunga di lettere univoche utilizzando Java. Ad esempio, la sottostringa più lunga di lettere univoche in "CODINGISAWESOME" è "NGISAWE".

2. Approccio a forza bruta

Cominciamo con un approccio ingenuo. Per cominciare, possiamo esaminare ogni sottostringa se contiene caratteri univoci:

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

Poiché ci sono n * (n + 1) / 2 possibili sottostringhe, la complessità temporale di questo approccio è O (n ^ 2) .

3. Approccio ottimizzato

Ora, diamo un'occhiata a un approccio ottimizzato. Iniziamo ad attraversare la stringa da sinistra a destra e manteniamo traccia di:

  1. la sottostringa corrente con caratteri non ripetitivi con l'aiuto di un indice di inizio e di fine
  2. l' output di sottostringa non ripetibile più lungo
  3. una tabella di ricerca di caratteri già visitati
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; }

Per ogni nuovo personaggio, lo cerchiamo nei personaggi già visitati. Se il personaggio è già stato visitato e fa parte della sottostringa corrente con caratteri non ripetitivi, aggiorniamo l'indice iniziale. Altrimenti, continueremo ad attraversare la stringa.

Poiché stiamo attraversando la stringa solo una volta, la complessità temporale sarà lineare, o O (n) .

Questo approccio è noto anche come modello di finestra scorrevole.

4. Test

Infine, testiamo a fondo la nostra implementazione per assicurarci che funzioni:

@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")); }

Qui, proviamo a testare le condizioni al contorno così come i casi d'uso più tipici .

5. conclusione

In questo tutorial, abbiamo imparato come utilizzare la tecnica della finestra scorrevole per trovare la sottostringa più lunga con caratteri non ripetitivi.

E, come sempre, il codice sorgente è disponibile su GitHub.