First Unique Character in a String

+10

Otrzymujesz ciąg znaków s złożony z małych liter alfabetu angielskiego. Znajdź pierwszy znak, który występuje w całym ciągu dokładnie raz, i zwróć jego indeks, licząc od 0. Jeśli każdy znak występuje więcej niż raz, zwróć -1.

Funkcja

firstUniqChar(s: string) → integer

sstring: ciąg znaków do wyszukania, wyłącznie małe litery
Zwracainteger: indeks pierwszej litery, która występuje dokładnie raz, lub -1, jeśli takiej nie ma

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera wyłącznie małe litery alfabetu angielskiego (a–z).

Przykłady

Wejście: s = "coddycode"
Wyjście: 4
Wyjaśnienie: W coddycode litery c i o występują dwa razy, d trzy razy, a e raz, na indeksie 8. Ale y również występuje raz, na indeksie 4, i pojawia się jako pierwsze, więc odpowiedź to 4.

Wejście: s = "swiss"
Wyjście: 1
Wyjaśnienie: W swiss litera s występuje trzy razy. Litera w o indeksie 1 pojawia się raz, podobnie jak i o indeksie 2; wygrywa pierwsza z nich, więc odpowiedź to 1.

Wejście: s = "aabbcc"
Wyjście: -1
Wyjaśnienie: Każda litera w aabbcc występuje dwa razy, więc żaden znak nie jest unikalny, a odpowiedzią jest -1.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Znaki napływają pojedynczo ze strumienia, a po każdym z nich musisz podać pierwszy unikalny znak do tej pory. Jak aktualizować odpowiedź na bieżąco?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Litera, która wydaje się unikalna, gdy do niej dotrzesz, może powtórzyć się na samym końcu ciągu znaków, więc jedno spojrzenie od lewej do prawej nie wystarczy. Najpierw policz każdą literę, a wtedy drugie przejście pozwoli w stałym czasie ustalić, czy na każdej pozycji znajduje się unikalna litera.

Poszukaj drugiej kopii każdej litery

Poprawne, ale nie kończy się na największych testach

Intuicja

Przejdź po pozycjach od lewej. Dla pozycji i przeszukaj cały ciąg znaków w poszukiwaniu innej pozycji j z tą samą literą. Jeśli jej nie ma, s[i] jest unikalna, a ponieważ idziesz od lewej, jest to pierwsza unikalna litera: zwróć i. W ciągu coddycode pozycje od 0 do 3 znajdują kopię, a pozycja 4, czyli y, nie znajduje żadnej.

Przeszukiwanie musi obejmować cały ciąg znaków, przed pozycją i i za nią. Wcześniejsza kopia w ciągu dyskwalifikuje literę tak samo jak późniejsza.

Kończenie przeszukiwania przy pierwszej kopii pomaga w przypadku większości ciągów, ale nie wszystkich. Gdy każda litera występuje w jednym długim ciągu, na przykład 2000 liter a, następnie 2000 liter b i tak dalej, wyszukiwanie dla każdej litery przechodzi przez wszystkie wcześniejsze ciągi liter, zanim znajdzie kopię. Dla n = 5 × 10^4 oznacza to ponad miliard porównań, co jest zbyt wolne dla największych testów.

Algorytm

Dla każdego indeksu i, od lewej do prawej:
Sprawdź każdy indeks j inny niż i i zatrzymaj się na pierwszym, dla którego s[j] jest równe s[i].
Jeśli nie istnieje takie j, zwróć i.
Jeśli dla każdego indeksu znaleziono kopię, zwróć -1.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

Policz litery, a następnie przeskanuj

Intuicja

Metoda siłowa ponownie pyta dla każdej pozycji: „czy ta litera pojawia się gdzieś jeszcze?”. Zamiast tego policz wystąpienia tylko raz. Istnieje tylko 26 liter, więc tablica 26 liczników przechowuje wszystkie liczby wystąpień, przy czym indeks 0 odpowiada a, a indeks 25 — z. Indeks litery to jej kod znaku pomniejszony o kod a.

Pierwsze przejście wypełnia liczniki. Dla coddycode ich wartości to: c: 2, o: 2, d: 3, y: 1, e: 1. Drugie przejście przegląda ciąg od lewej strony i zatrzymuje się na pierwszej pozycji, której litera ma licznik równy 1. Jest to y na indeksie 4. Drugie przejście musi przeglądać ciąg, a nie 26 liczników, ponieważ chodzi o pierwszą pozycję, a nie pierwszą literę alfabetu.

Oba przejścia odczytują ciąg jeden raz, więc czas działania wynosi O(n). Liczba liczników zawsze wynosi 26, niezależnie od długości ciągu, więc dodatkowe zużycie pamięci to O(1).

Algorytm

Utwórz tablicę złożoną z 26 zer.
Dla każdej litery w s zwiększ jej licznik o 1.
Przejdź ponownie przez s, zaczynając od indeksu 0. Zwróć pierwszy indeks, którego litera ma licznik równy 1.
Jeśli przejście dobiegnie końca, zwróć -1.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

Pułapki i przypadki brzegowe

Większość błędów wynika ze zbyt wczesnego podjęcia decyzji albo przejścia po niewłaściwym elemencie w drugim przebiegu.

Sprawdzanie tylko liter przed pozycją i. W abca pierwsze a nie ma przed sobą kopii, a mimo to nie jest unikalne.
Przechodzenie po tablicy liczników zamiast po ciągu znaków w drugim przebiegu. Dla ba pierwszy licznik równy 1 należy do a, ale odpowiedzią jest indeks 0, czyli b.
Zwracanie litery zamiast jej indeksu albo zwracanie indeksu liczonego od 1. Lua i R liczą od 1, więc przed zwróceniem odejmij 1.
Zapominanie o przypadku -1. Ciąg taki jak aabbcc nie zawiera żadnej unikalnej litery, a funkcja musi mimo to zwrócić wartość po zakończeniu pętli.
Indeksowanie liczników za pomocą surowego kodu znaku. a ma kod 97, który znacznie wykracza poza koniec tablicy o długości 26; najpierw odejmij kod znaku a.

Najczęstsze pytania4

Jaka jest złożoność czasowa zadania „Pierwszy unikalny znak w ciągu znaków”?

Liczenie liter, a następnie skanowanie ciągu znaków to dwa przebiegi po n kroków każdy, więc czas wynosi O(n). 26 liczników zajmuje tyle samo miejsca niezależnie od długości ciągu, więc dodatkowa przestrzeń wynosi O(1).

Czy potrafisz rozwiązać to w jednym przebiegu po ciągu znaków?

Tak. W jednym przebiegu zapisz dla każdej litery indeks jej pierwszego wystąpienia lub oznacz ją jako powtórzoną, gdy pojawi się ponownie. Następnie sprawdź 26 liter i wybierz najmniejszy indeks spośród tych, które wystąpiły tylko raz. Ciąg znaków jest odczytywany raz, a końcowe sprawdzenie zajmuje 26 kroków.

Czy do zliczania liter użyć mapy haszującej czy tablicy?

W przypadku samych małych liter tablica 26 liczników jest mniejsza i szybsza niż mapa mieszająca. Mapa mieszająca jest właściwym wyborem, gdy ciąg może zawierać dowolne znaki, na przykład tekst Unicode. Algorytm pozostaje taki sam: policz, a następnie przeskanuj ciąg.

Dlaczego drugi przebieg przechodzi przez ciąg znaków, a nie przez liczniki?

Liczniki informują tylko o tym, które litery są unikalne, a nie gdzie się znajdują. Odpowiedzią jest unikalna litera, która występuje jako pierwsza w ciągu, więc musisz przejść przez ciąg po kolei i zatrzymać się na pierwszej pozycji, na której litera ma licznik równy 1.

Python

def firstUniqChar(s):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s = "coddycode"

Oczekiwane