Algorytmy i struktury danych · Middle · Pytanie 18 z 75
Najdłuższy podnapis bez powtarzających się znaków: jaki jest pomysł na O(n)?
- 1Wygenerować wszystkie podnapisy i sprawdzić każdy na duplikaty
- ✓Poprawna odpowiedź: Przy powtórce przesunąć lewą granicę okna za poprzednią pozycję znaku
- 3Posortować znaki i policzyć najdłuższą serię
Wyjaśnienie
Przechowuj ostatni indeks każdego znaku w mapie. Gdy bieżący znak był już w oknie, przenieś lewą granicę na last + 1. Każdy indeks przesuwa się tylko do przodu, więc łączna praca to O(n).