Partition Labels

+10

Du erhältst eine Zeichenfolge s aus Kleinbuchstaben. Teile sie in so viele zusammenhängende Abschnitte wie möglich auf, sodass jeder Buchstabe nur in einem Abschnitt vorkommt: Wenn ein Buchstabe in einem Abschnitt auftaucht, befinden sich alle seine Vorkommen in diesem Abschnitt. Gib die Längen der Abschnitte von links nach rechts zurück.

Funktion

partitionLabels(s: string) → integer-array

sstring: die zu kürzende Zeichenfolge, nur Kleinbuchstaben
Gibt zurückinteger-array: die Länge jedes Teils, von links nach rechts

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Kleinbuchstaben.
Die Teile behalten ihre Reihenfolge und ergeben zusammen s, sodass sich ihre Längen zu s.length addieren.

Beispiele

Eingabe: s = "abacdcefe"
Ausgabe: [3, 3, 3]
Erklärung: Die a stehen an den Positionen 0 und 2, die c an den Positionen 3 und 5 und die e an den Positionen 6 und 8, also liegen die Schnitte nach aba und nach cdc. Kein Teil kann noch einmal geschnitten werden, da jedes mit demselben Buchstaben beginnt und endet.

+14 versteckte Tests beim Einreichen

Tipps

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

0 von 3 geöffnet

Lösung

Ein Schnitt ist nur dort zulässig, wo auf beiden Seiten davon kein Buchstabe vorkommt, und die beste Antwort setzt an jeder solchen Stelle einen Schnitt. Jede Stelle durch erneutes Durchlaufen der Zeichenkette zu testen, erfordert quadratische Laufzeit. Speichere zuerst die letzte Position jedes Buchstabens, und ein einziger Durchlauf von links nach rechts findet alle Schnittstellen, denn ein Abschnitt muss bis zum letzten Vorkommen jedes darin enthaltenen Buchstabens reichen.

Prüfe jede Lücke

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

Idee

Zwischen benachbarten Buchstaben gibt es n-1 Lücken. Ein Schnitt in einer Lücke ist nur erlaubt, wenn kein Buchstabe auf beiden Seiten davon vorkommt, da ein durch den Schnitt geteilter Buchstabe sonst in zwei Teilen läge. Wenn du an jeder erlaubten Stelle schneidest, erhältst du die meisten Teile. Betrachte ein Stück zwischen zwei benachbarten erlaubten Schnitten: Keiner seiner Buchstaben kommt links vom linken Schnitt oder rechts vom rechten Schnitt vor, also befinden sich alle Vorkommen innerhalb des Stücks und es ist ein gültiger Teil. Und jede gültige Antwort kann nur an erlaubten Lücken schneiden, daher hat keine Antwort mehr Teile.

Prüfe also jede Lücke: Sammle die Buchstaben links und rechts davon und schneide, wenn die beiden Mengen keine gemeinsamen Elemente haben. In abacdcefe stehen links von der Lücke nach aba a und b und rechts davon c, d, e und f. Es gibt keine gemeinsamen Buchstaben, also schneidest du. Links und rechts von der Lücke nach ab steht jeweils ein a, also schneidest du nicht.

Bei jeder Prüfung wird die gesamte Zeichenfolge durchlaufen, und es gibt n-1 Lücken. Daher werden ungefähr n² Buchstaben gelesen. Bei 50.000 Buchstaben sind das 2.5 × 10^9 Lesevorgänge – viel zu langsam für die größten Testfälle.

Algorithmus

Setze start = 0, dort beginnt der aktuelle Teil.
Markiere für jede Lücke cut von 1 bis n-1 (die Lücke direkt vor s[cut]) die Buchstaben von s[0..cut-1] und die Buchstaben von s[cut..n-1].
Wenn auf beiden Seiten kein Buchstabe markiert ist, addiere cut-start zur Antwort und setze start = cut.
Addiere nach der Schleife den letzten Teil, n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Füge die Spannen der einzelnen Buchstaben zusammen

Idee

Stell dir jeden Buchstaben als Intervall vor, vom ersten bis zum letzten Vorkommen. Ein Teil, der einen Buchstaben enthält, muss das gesamte Intervall abdecken. Zwei Buchstaben, deren Intervalle sich überschneiden, müssen also zum selben Teil gehören, und die Überschneidung breitet sich aus: Wenn a sich mit b und b sich mit c überschneidet, landen alle drei im selben Teil.

Das ist das Problem des Zusammenführens von Intervallen. Erfasse in einem Durchlauf die erste und letzte Position jedes Buchstabens. Betrachte dann die Intervalle in der Reihenfolge ihres Anfangs und füge diejenigen zusammen, die sich überschneiden. Jeder zusammengeführte Block ist ein Teil, und die Lücken zwischen den Blöcken sind genau die zulässigen Schnittstellen. Du erhältst die Intervalle ohne Sortieren in der Reihenfolge ihres Anfangs: Gehe die Zeichenfolge erneut durch und nimm das Intervall eines Buchstabens, wenn du an seiner ersten Position bist.

In codingisfun lauten die Intervalle in dieser Reihenfolge: c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] und u [9, 9]. Die ersten drei stehen für sich allein. Ab i beginnt jedes Intervall bei Position 10 oder davor, wo n endet, daher werden sie zu [3, 10] zusammengeführt, einem Teil mit 8 Buchstaben.

Die Zeichenfolge enthält höchstens 26 verschiedene Buchstaben, also gibt es höchstens 26 Intervalle, und die Tabellen mit den ersten und letzten Positionen haben eine feste Größe.

Algorithmus

Erfasse in einem Durchlauf über s first und last, die erste und letzte Position jedes Buchstabens.
Durchlaufe s erneut. Wenn Position i die erste Position ihres Buchstabens ist, ist das Intervall dieses Buchstabens [i, last] das nächste in der Reihenfolge der Startpositionen.
Wenn das Intervall nach dem end des aktuellen Blocks beginnt, schließe den Block mit der Länge end-start+1 und beginne bei i einen neuen Block.
Setze in jedem Fall end = max(end, last).
Schließe den letzten Block und gib die Längen zurück.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Erweitere jeden Teil bis zu seinem letzten Buchstaben

Idee

Die ersten Positionen werden gar nicht benötigt. Lies den String von links nach rechts und behalte end, die am weitesten rechts liegende letzte Position eines Buchstabens im aktuellen Teil. Wenn du bei i einen Buchstaben liest, muss dessen letztes Vorkommen ebenfalls in diesem Teil liegen. Vergrößere also end auf last[s[i]], falls diese Position weiter rechts liegt.

Wenn i end erreicht, liegt das letzte Vorkommen jedes Buchstabens, den du in diesem Teil gelesen hast, bei i oder davor. Kein Buchstabe überschreitet die Lücke nach i, daher ist ein Schnitt dort erlaubt. Schließe den Teil mit der Länge end-start+1 ab und beginne den nächsten bei i+1.

Warum ist der Schnitt bei der ersten Gelegenheit die richtige Greedy-Entscheidung? Bevor i end erreicht, hat noch ein Buchstabe des Teils ein Vorkommen weiter rechts, daher ist kein früherer Schnitt erlaubt. Und der Durchlauf übersieht keine erlaubte Lücke: Wenn kein Buchstabe die Lücke nach i überschreitet, endet jeder Buchstabe des Teils bei i oder davor, also ist end genau dort gleich i. Der Durchlauf schneidet genau an den erlaubten Lücken, wodurch die größtmögliche Anzahl an Teilen entsteht.

In abacdcefe sind die letzten Positionen für a 2, b 1, c 5, d 4, e 8 und f 7. Beim Lesen von a wird end auf 2 gesetzt, b lässt den Wert unverändert, und bei i = 2 wird der Teil mit der Länge 3 abgeschlossen. Bei c wird end auf 5 gesetzt und der Teil endet bei 5, wieder mit der Länge 3. Der e-Teil endet bei 8.

Algorithmus

Speichere in einem Durchlauf last[c], die letzte Position jedes Buchstabens c, in einem Array der Länge 26.
Setze start = 0 und end = 0.
Setze für jede Position i end = max(end, last[s[i]]).
Wenn i == end gilt, addiere end-start+1 zur Antwort und setze start = i+1.
Gib die Längen zurück.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Stolperfallen und Grenzfälle

Der gierige Durchlauf ist kurz, daher verstecken sich die Fehler darin, mit welcher Position du vergleichst und wie lang die Teile sind.

Du schneidest, wenn du das letzte Vorkommen des aktuellen Buchstabens erreichst, statt das end des Teils. In abcba ist das c an Index 2 sein eigenes letztes Vorkommen, aber die a's reichen bis Index 4. Ein Schnitt an dieser Stelle würde also sowohl die a's als auch die b's trennen.
Ein Fehler um eins bei der Länge. Ein Teil von start bis end, wobei beide eingeschlossen sind, hat end-start+1 Buchstaben.
Du gibst die Schnittpositionen statt der Längen zurück. Für abacdcefe lautet die Antwort [3, 3, 3], nicht [2, 5, 8].
Du vergisst das letzte Teilstück, wenn du an Lücken schneidest. Nach dem letzten Teilstück kommt keine Lücke mehr, also addiere n-start, sobald die Schleife beendet ist.
Du erwartest ein Teilstück pro unterschiedlichem Buchstaben. zebraz hat fünf verschiedene Buchstaben und ein einziges Teilstück, denn die z's halten alles dazwischen zusammen.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Partition Labels?

Ein Durchlauf erfasst die letzte Position jedes Buchstabens und ein zweiter Durchlauf setzt die Schnittstellen, daher beträgt die Laufzeit O(n). Die Tabelle der letzten Positionen hat unabhängig von der Länge der Zeichenkette 26 Einträge, daher beträgt der zusätzliche Speicherplatz O(1), ohne die Ausgabe mitzuzählen.

Warum funktioniert der Greedy-Ansatz für Partition Labels?

Der aktuelle Teil muss das letzte Vorkommen jedes darin enthaltenen Buchstabens erreichen, daher ist kein Schnitt vor end erlaubt. Bei end kommt kein Buchstabe des Teils später noch einmal vor, daher ist der Schnitt erlaubt, und ihn zu setzen beeinträchtigt den Rest der Zeichenfolge nicht. Der Durchlauf setzt daher an jeder zulässigen Lücke einen Schnitt und nirgendwo sonst, wodurch die größtmögliche Anzahl an Teilen entsteht.

Ist Partition Labels ein Problem zum Zusammenführen von Intervallen?

Ja, in verkleideter Form. Jeder Buchstabe deckt das Intervall von seinem ersten bis zu seinem letzten Vorkommen ab, überlappende Intervalle müssen einen Abschnitt gemeinsam haben, und durch Zusammenführen erhält man genau die Abschnitte. Der Greedy-Durchlauf ist dasselbe Zusammenführen direkt während des Durchlaufs: end ist der rechte Rand des bisher zusammengeführten Blocks.

Wie viele Teile kann Partition Labels zurückgeben?

Zwischen 1 und 26. Kein Buchstabe kann in zwei Teilen vorkommen, daher besitzt jeder Teil mindestens einen eigenen Buchstaben, und es gibt nur 26 Kleinbuchstaben. Eine Zeichenfolge, in der jeder Buchstabe einmal vorkommt, ergibt 26 Teile der Länge 1, und eine Zeichenfolge, die mit demselben Buchstaben beginnt und endet, ergibt einen einzigen Teil.

Python

def partitionLabels(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "abacdcefe"

Erwartet

[3, 3, 3]

Partition Labels

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Prüfe jede Lücke

Füge die Spannen der einzelnen Buchstaben zusammen

Erweitere jeden Teil bis zu seinem letzten Buchstaben

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben