First Unique Character in a String

+10

Du erhältst eine Zeichenfolge s aus englischen Kleinbuchstaben. Finde das erste Zeichen, das genau einmal in der gesamten Zeichenfolge vorkommt, und gib seinen Index zurück, gezählt ab 0. Wenn jedes Zeichen mehr als einmal vorkommt, gib -1 zurück.

Funktion

firstUniqChar(s: string) → integer

sstring: die zu durchsuchende Zeichenfolge, nur Kleinbuchstaben
Gibt zurückinteger: der Index des ersten Buchstabens, der genau einmal vorkommt, oder -1, falls es keinen gibt

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Kleinbuchstaben (a bis z).

Beispiele

Eingabe: s = "coddycode"
Ausgabe: 4
Erklärung: In coddycode kommen die Buchstaben c und o zweimal vor, d dreimal und e einmal, an Index 8. Aber auch y kommt einmal vor, an Index 4, und es kommt zuerst, daher lautet die Antwort 4.

Eingabe: s = "swiss"
Ausgabe: 1
Erklärung: In swiss kommt der Buchstabe s dreimal vor. Der Buchstabe w an Index 1 kommt einmal vor, ebenso i an Index 2; der erste von beiden gewinnt, also lautet die Antwort 1.

Eingabe: s = "aabbcc"
Ausgabe: -1
Erklärung: Jeder Buchstabe in aabbcc kommt zweimal vor, daher ist kein Zeichen eindeutig und die Antwort lautet -1.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Die Zeichen treffen nacheinander aus einem Datenstrom ein, und nach jedem Zeichen musst du das erste bisher eindeutige Zeichen angeben. Wie würdest du die Antwort stets aktuell halten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Buchstabe, der eindeutig wirkt, wenn du ihn erreichst, kann ganz am Ende der Zeichenfolge erneut vorkommen, daher reicht ein einzelner Blick von links nach rechts nicht aus. Zähle zuerst jeden Buchstaben, dann kann der zweite Durchgang in konstanter Zeit feststellen, ob jede Position einen eindeutigen Buchstaben enthält.

Suche nach einer zweiten Kopie jedes Buchstabens

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Gehe die Positionen von links durch. Durchsuche für die Position i die gesamte Zeichenfolge nach einer anderen Position j mit demselben Buchstaben. Gibt es keine, ist s[i] eindeutig, und da du von links gehst, ist es der erste eindeutige Buchstabe: Gib i zurück. In coddycode findet jede der Positionen 0 bis 3 eine Kopie, und Position 4, das y, findet keine.

Die Suche muss die gesamte Zeichenfolge abdecken, also auch die Bereiche vor und nach i. Eine frühere Kopie in der Zeichenfolge disqualifiziert den Buchstaben genauso wie eine spätere.

Bei den meisten Zeichenfolgen ist es hilfreich, beim ersten Fund einer Kopie abzubrechen, aber nicht bei allen. Wenn jeder Buchstabe in einem langen Block vorkommt, etwa 2000 as, dann 2000 bs und so weiter, durchläuft die Suche für jeden Buchstaben alle vorherigen Blöcke, bevor sie eine Kopie findet. Bei n = 5 × 10^4 sind das über eine Milliarde Vergleiche – zu langsam für die größten Tests.

Algorithmus

Für jeden Index i von links nach rechts:
Durchsuche jeden Index j außer i und halte beim ersten an, bei dem s[j] gleich s[i] ist.
Wenn es kein solches j gibt, gib i zurück.
Wenn jeder Index eine Kopie gefunden hat, gib -1 zurück.

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

Buchstaben zählen, dann scannen

Idee

Die Brute-Force-Methode fragt für jede Position erneut: „Kommt dieser Buchstabe irgendwo anders vor?“ Zähle stattdessen einmal. Es gibt nur 26 Buchstaben, daher enthält ein Array mit 26 Zählern alle Häufigkeiten, mit Index 0 für a und Index 25 für z. Der Index eines Buchstabens ist sein Zeichencode abzüglich des Codes von a.

Der erste Durchlauf füllt die Zähler. Für coddycode lauten sie: c: 2, o: 2, d: 3, y: 1, e: 1. Der zweite Durchlauf geht den String von links durch und hält bei der ersten Position an, deren Buchstabe eine Häufigkeit von 1 hat. Das ist y am Index 4. Der zweite Durchlauf muss den String durchgehen, nicht die 26 Zähler, denn es geht um die erste Position und nicht um den ersten Buchstaben im Alphabet.

Beide Durchläufe lesen den String einmal, daher beträgt die Laufzeit O(n). Die Anzahl der Zähler bleibt unabhängig von der Länge des Strings bei 26, daher beträgt der zusätzliche Speicherplatz O(1).

Algorithmus

Erstelle ein Array aus 26 Nullen.
Erhöhe für jeden Buchstaben von s seinen Zähler um 1.
Durchlaufe s erneut ab Index 0. Gib den ersten Index zurück, dessen Buchstabe eine Häufigkeit von 1 hat.
Wenn der Durchlauf endet, gib -1 zurück.

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

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen, wenn man sich zu früh festlegt oder im zweiten Durchlauf das Falsche durchläuft.

Es werden nur die Buchstaben vor Position i überprüft. In abca gibt es vor dem ersten a kein weiteres, und dennoch ist es nicht eindeutig.
Im zweiten Durchlauf wird das Zähler-Array statt des Strings durchlaufen. Bei ba gehört der erste Zähler mit dem Wert 1 zu a, aber die Antwort ist Index 0, also das b.
Es wird der Buchstabe statt seines Index zurückgegeben oder der Index wird ab 1 gezählt. Lua und R beginnen bei 1, also ziehe vor der Rückgabe 1 ab.
Der Fall -1 wird vergessen. Ein String wie aabbcc enthält keinen eindeutigen Buchstaben, und die Funktion muss nach der Schleife trotzdem einen Wert zurückgeben.
Die Zähler werden mit dem unveränderten Zeichencode indiziert. a hat den Wert 97 und liegt damit weit außerhalb eines Arrays mit 26 Elementen; ziehe zuerst den Zeichencode von a ab.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Erstes eindeutiges Zeichen in einer Zeichenfolge“?

Die Buchstaben zu zählen und anschließend die Zeichenfolge zu durchlaufen, erfordert jeweils n Schritte, also beträgt die Laufzeit O(n). Die 26 Zähler benötigen unabhängig von der Länge denselben Speicherplatz, sodass der zusätzliche Speicherplatz O(1) beträgt.

Kannst du es in einem einzigen Durchlauf über den String lösen?

Ja. Durchlaufe den String einmal und speichere für jeden Buchstaben den Index seines ersten Auftretens oder markiere ihn als wiederholt, wenn er erneut vorkommt. Überprüfe dann die 26 Buchstaben und nimm den kleinsten Index unter denen, die genau einmal vorkamen. Der String wird einmal gelesen, und die abschließende Überprüfung kostet 26 Schritte.

Solltest du eine Hash-Map oder ein Array verwenden, um die Buchstaben zu zählen?

Bei ausschließlich Kleinbuchstaben ist ein Array mit 26 Zählern kleiner und schneller als eine Hashmap. Eine Hashmap ist die richtige Wahl, wenn die Zeichenfolge beliebige Zeichen enthalten kann, etwa Unicode-Text. Der Algorithmus bleibt derselbe: zählen und dann die Zeichenfolge durchlaufen.

Warum läuft der zweite Durchlauf über die Zeichenkette und nicht über die Zählwerte?

Die Häufigkeiten sagen nur aus, welche Buchstaben einzigartig sind, nicht, an welcher Stelle sie stehen. Gesucht ist der einzigartige Buchstabe, der in der Zeichenkette zuerst vorkommt. Deshalb musst du die Zeichenkette der Reihe nach durchlaufen und an der ersten Position anhalten, an der ein Buchstabe die Häufigkeit 1 hat.

Python

def firstUniqChar(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "coddycode"

Erwartet