Algorithmen und Datenstrukturen · Middle · Frage 18 von 75
Längster Teilstring ohne wiederholte Zeichen: was ist die O(n)-Idee?
- 1Alle Teilstrings erzeugen und jeden auf Duplikate prüfen
- 2Bei einer Wiederholung den linken Rand hinter die alte Position setzen
- 3Die Zeichen sortieren und ihre längste Folge zählen
Antwort zeigen
Richtige Antwort: Bei einer Wiederholung den linken Rand hinter die alte Position setzen
Erklärung
Speichere den letzten Index jedes Zeichens in einer Map. Wurde das aktuelle Zeichen im Fenster gesehen, springt der linke Rand auf last + 1. Jeder Index bewegt sich nur vorwärts, die Gesamtarbeit ist also O(n).