Najdłuższy podnapis bez powtórzeń
Śledzenie ostatnio widzianych pozycji w oknie
Najdłuższy podnapis bez powtórzeń to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Klasyczny problem z oknem
Należy znaleźć najdłuższy podłańcuch bez powtarzających się znaków. To popularny przykład okna przesuwnego, który pojawia się w niemal każdym systemie oceniania zadań. 🔤
Pułapka brutalnej siły
Sprawdzanie powtórzeń w każdym podłańcuchu ma koszt około O(n^2) lub większy. Dla długich napisów jest to zdecydowanie zbyt wolne, dlatego potrzebne jest sprytniejsze przejście.
Okno unikatowych znaków
Należy utrzymywać okno zawierające wyłącznie różne znaki. Okno rozszerza się w prawo, a gdy pojawi się powtórzenie, należy zmniejszać je od lewej, aż powtórzenie zniknie.
Zapamiętywanie ostatnich pozycji
Należy przechowywać ostatni indeks każdego znaku w słowniku. Dzięki temu podczas przejścia można natychmiast ustalić, gdzie ostatnio widziano powtórzenie.
last = {}
left = 0
best = 0Przejście po każdym znaku
Należy przechodzić po napisie za pomocą right, odczytując w każdej iteracji zarówno indeks, jak i znak znajdujący się na tej pozycji. To przesuwa okno o jedną pozycję naraz.
for right, ch in enumerate(s):Przeskok lewego wskaźnika
Jeśli znak został znaleziony wewnątrz bieżącego okna, należy przesunąć left tuż za jego ostatnią pozycję. W ten sposób powtórzenie zostaje usunięte jednym ruchem.
if ch in last and last[ch] >= left:
left = last[ch] + 1Aktualizacja i pomiar
Należy zapisać nową pozycję tego znaku, po czym okno od left do right nie zawiera już powtórzeń. Jego długość wynosi right minus left plus jeden.
last[ch] = right
best = max(best, right - left + 1)Dlaczego warunek ochronny ma znaczenie
Sprawdzenie last[ch] >= left jest niezbędne. Bez niego stara pozycja spoza okna niesłusznie przesunęłaby left wstecz.
Liniowy czas i liniowa pamięć
Każdy znak jest odwiedzany raz, a left porusza się wyłącznie do przodu, więc przejście ma koszt O(n). Słownik zajmuje pamięć proporcjonalną do liczby różnych znaków.
Przypadki brzegowe
Pusty napis daje wynik zero, a napis złożony z jednego powtarzającego się znaku daje wynik jeden. Przed wysłaniem rozwiązania należy sprawdzić oba przypadki, aby uniknąć podstępnego WA.
Uniwersalny schemat
Mapa ostatnich wystąpień wraz ze skokowym przesuwaniem left znajduje zastosowanie w wielu zadaniach dotyczących różności, na przykład w oknach zawierających najwyżej jedno powtórzenie.
Szybkie sprawdzenie
Podczas wyszukiwania najdłuższego unikatowego podłańcucha śledzą Państwo ostatni indeks każdego znaku.
Podsumowanie
Należy przesuwać okno różnych znaków, zapisywać każdą ostatnią pozycję i przeskakiwać wskaźnikiem left za powtórzenia. W ten sposób klasyczny problem można rozwiązać w czasie O(n). ✅
Często zadawane pytania
Czy lekcja „Najdłuższy podnapis bez powtórzeń” jest bezpłatna?
Tak — pełny tekst „Najdłuższy podnapis bez powtórzeń” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Najdłuższy podnapis bez powtórzeń”?
Śledzenie ostatnio widzianych pozycji w oknie Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Najdłuższy podnapis bez powtórzeń”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sumy okien o stałym rozmiarze
- Zmienny zakres okna z dwoma wskaźnikami
- Najdłuższy podnapis bez powtórzeń
- Zliczanie okien spełniających regułę