Longest Repeating Character Replacement

+10

Du erhältst eine Zeichenfolge s aus englischen Großbuchstaben und eine ganze Zahl k. Du darfst höchstens k Positionen in s auswählen und den Buchstaben an jeder dieser Positionen durch einen beliebigen anderen Großbuchstaben ersetzen.

Gib die Länge des längsten Teilstrings zurück, also einer Folge direkt aufeinanderfolgender Buchstaben, die nach deinen Änderungen nur aus demselben wiederholten Buchstaben besteht.

Funktion

characterReplacement(s: string, k: integer) → integer

sstring: die Zeichenkette aus Großbuchstaben
kinteger: die meisten Buchstaben, die du ändern darfst
Gibt zurückinteger: die Länge des längsten Teilstrings aus demselben wiederholten Buchstaben, den du bilden kannst

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Großbuchstaben.
0 ≤ k ≤ s.length

Beispiele

Eingabe: s = "BAAACAB"k = 1
Ausgabe: 5
Erklärung: Ändere das C in ein A, und an den Indizes 1 bis 5 steht AAAAA. Für sechs Buchstaben wären zwei Änderungen nötig: An den Indizes 0 bis 5 stehen ein B und das C, und an den Indizes 1 bis 6 stehen das C und das letzte B.

Eingabe: s = "AABBBAB"k = 2
Ausgabe: 6
Erklärung: In ABBBAB, den Indizes 1 bis 6, sind die beiden As die einzigen Buchstaben, die nicht B sind, also ergeben zwei Änderungen BBBBBB. Die gesamte Zeichenfolge enthält drei As und vier Bs, also sind drei Änderungen nötig.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Was ändert sich, wenn s jedes beliebige Zeichen enthalten kann und nicht nur die 26 Großbuchstaben?

Tipps

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

0 von 3 geöffnet

Lösung

Die Kosten für eine Teilzeichenfolge sind leicht zu erkennen: ihre Länge minus der Anzahl ihres häufigsten Buchstabens. Der schwierige Teil ist, nicht für alle n² Teilzeichenfolgen zu bezahlen. Ein gleitendes Fenster durchläuft die Zeichenfolge einmal, und die beste Variante beruht auf zwei Tatsachen: Das Fenster muss nie verkleinert werden, und die höchste Buchstabenanzahl muss nie sinken.

Jeden Teilstring überprüfen

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

Idee

Ändere ein Teilstück. Zu welchem Buchstaben sollte es werden? Zu dem, der bereits am häufigsten vorkommt, denn jeder andere Buchstabe muss geändert werden. Ein Teilstück der Länge len, in dem der häufigste Buchstabe top-mal vorkommt, benötigt also len - top Änderungen und ist erreichbar, wenn dieser Wert höchstens k beträgt.

Probiere jedes Teilstück aus. Beginne für jeden Startpunkt und erweitere das Ende Buchstabe für Buchstabe. Dabei führst du eine Häufigkeitszählung für jeden Buchstaben und erhöhst top nach Bedarf. So erfordert jedes neue Teilstück nur eine Aktualisierung statt einer neuen Zählung. Jedes Teilstück wird überprüft, sodass das längste erreichbare nicht übersehen werden kann.

Das ist langsam, weil eine Zeichenkette der Länge n etwa n²/2 Teilstücke hat. Für n = 5 × 10^4 sind das 1.25 × 10^9 Überprüfungen – weit mehr, als das Zeitlimit zulässt.

Algorithmus

Setze best auf 0.
Setze für jeden Startindex die 26 Zähler und top auf 0 zurück.
Bewege end vom Start bis zum letzten Index. Addiere s[end] zu seinem Zähler und erhöhe top, wenn dieser Zähler nun den höchsten Wert hat.
Wenn end - start + 1 - top ≤ k, ist der Teilstring erreichbar: Speichere seine Länge, wenn sie größer als best ist.
Gib best zurück.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

Ein gleitendes Fenster pro Zielbuchstabe

Idee

Drehe die Frage um und wähle zuerst den Buchstaben. Wenn der endgültige Lauf nur aus A besteht, lautet die Frage: Was ist die längste Teilzeichenfolge mit höchstens k Buchstaben, die nicht A sind? Das ist ein klassisches Sliding-Window-Verfahren.

Bewege right über die Zeichenfolge und zähle die Buchstaben im Fenster, die nicht dem Zielbuchstaben entsprechen. Wenn diese Anzahl größer als k wird, bewege left nach vorne, bis sie wieder k beträgt. Ein wachsendes Fenster kann nur weitere Buchstaben hinzufügen, die geändert werden müssen. Deshalb bleibt ein Fenster, dessen Änderung zu aufwendig ist, auch dann zu aufwendig, wenn es wächst, und left muss sich nie zurückbewegen. Für jedes right ist das beibehaltene Fenster das längste gültige Fenster, das dort endet.

Führe dies für alle 26 Buchstaben aus und merke dir die größte Länge. Jeder Durchlauf benötigt O(n), also sind es insgesamt 26 Durchläufe, etwa 1.3 × 10^6 Schritte für n = 5 × 10^4. Das ist linear, aber die Zeichenfolge wird 26-mal gelesen, und das funktioniert nur, weil das Alphabet klein ist.

Algorithmus

Starte für jeden Ziellbuchstaben von A bis Z ein Fenster mit left = 0 und others = 0.
Bewege right über den String. Wenn s[right] nicht der Ziellbuchstabe ist, erhöhe others um eins.
Solange others > k gilt, bewege left weiter und verringere others um eins, wenn der Buchstabe, der das Fenster verlässt, nicht der Ziellbuchstabe ist.
Speichere right - left + 1, wenn der Wert größer als best ist.
Gib nach allen 26 Buchstaben best zurück.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

Ein Fenster, das nie kleiner wird

Idee

Berücksichtige jeden Buchstaben in einem Fenster. Zähle darin jeden der 26 Buchstaben und speichere top, den höchsten Zählerstand. Für das Fenster sind length - top Änderungen nötig, daher ist es gültig, wenn dieser Wert höchstens k beträgt.

Erste Erkenntnis: Das Fenster muss nie schrumpfen. Es geht nur darum, die bisher gefundene beste Länge zu übertreffen. Wenn das Hinzufügen von s[right] das Fenster zu teuer macht, entferne links einen Buchstaben. Das Fenster verschiebt sich um einen Schritt und behält seine Länge. Ist das Fenster nicht zu teuer, wächst es um eins. Seine Länge entspricht daher immer der bisher gefundenen besten Länge, und am Ende lautet die Antwort n - left.

Zweite Erkenntnis: top muss nie kleiner werden. Wenn links ein Buchstabe das Fenster verlässt, lässt du top unverändert, sodass der Wert höher sein kann als der tatsächliche Zählerstand im Fenster. Das ist unproblematisch. Nach einer Verschiebung ist die Länge des Fensters genau top + k. Damit es wachsen kann, muss also ein Buchstabe hinzukommen, der top + 1 Mal im Fenster vorkommt; in diesem Moment steigt auch top. Ein veralteter Wert für top kann dazu führen, dass sich das Fenster verschiebt, aber niemals irrtümlich wächst. Durch die Verschiebung geht nichts verloren, denn nur ein längeres Fenster könnte den bisherigen Rekord übertreffen.

Bei BAAACAB mit k = 1 wächst das Fenster zunächst auf BAAA. Für BAAAC sind dann 2 Änderungen nötig, also verschiebt es sich zu AAAC. Durch das Hinzufügen des nächsten A steigt top auf 4, und das Fenster wächst auf AAACA mit der Länge 5. Das letzte B bewirkt eine weitere Verschiebung, also lautet die Antwort 5.

Algorithmus

Behalte die 26 Zähler, left = 0 und top = 0 bei.
Bewege right über den String: Addiere s[right] zu seinem Zähler und erhöhe top, wenn dieser Zähler nun höher ist.
Wenn right - left + 1 - top > k, sind zu viele Änderungen für das Fenster nötig: Entferne s[left] aus den Zählern und bewege left um einen Schritt weiter. Das Fenster verschiebt sich und behält seine Länge bei.
Verringere top niemals, wenn ein Buchstabe das Fenster verlässt.
Gib die Länge des endgültigen Fensters zurück: n - left.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

Stolperfallen und Grenzfälle

Der Fenstercode ist kurz, daher entstehen die meisten falschen Antworten durch die Kostenformel oder eine Abkürzung, die nur richtig aussieht.

k zum längsten Lauf addieren. Bei AAAB mit k = 3 ergibt das 6, also mehr als die Länge der Zeichenfolge. Bei BAAACAB mit k = 1 ergibt das 4, aber die richtige Änderung liegt in der Mitte und verbindet zwei Läufe zu einem Lauf der Länge 5.
Änderungen anhand des ersten Buchstabens des Fensters zählen, statt anhand seines häufigsten Buchstabens. Das Fenster BAAA benötigt eine Änderung, nicht drei.
n - left aus einer Version zurückgeben, deren Fenster schrumpfen kann. Diese Abkürzung funktioniert nur, wenn das Fenster nie kürzer wird, wie beim Ein-Fenster-Code hier. Wenn deine Schleife das Fenster mit while verkleinert und das tatsächliche Maximum neu berechnet, verwende ein separates best.
Die Fensterlänge als right - left messen. Beide Enden gehören zum Fenster, also addiere eins.
k = 0 als Sonderfall behandeln. Ohne Änderungen gibt die Fensterregel bereits den längsten Lauf eines einzelnen Buchstabens zurück.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Longest Repeating Character Replacement?

Die Lösung mit einem Fenster läuft in O(n), wobei n die Länge von s ist: right besucht jeden Buchstaben einmal und left bewegt sich pro Schritt höchstens einmal. Sie benötigt O(1) zusätzlichen Speicherplatz: 26 Zähler und einige Ganzzahlen.

Warum muss die maximale Häufigkeit nicht aktualisiert werden, wenn das Fenster verschoben wird?

Das Fenster versucht nur, seinen eigenen Rekord zu übertreffen. Nach einem Verschieben beträgt seine Länge top + k, daher muss in einem längeren gültigen Fenster ein Buchstabe mehr als top Mal vorkommen, wodurch top ohnehin erhöht wird. Ein zu hoher Wert für top hält das Fenster lediglich auf seiner Länge; er lässt es niemals wachsen, wenn es das nicht sollte.

Worin unterscheidet sich das von „Longest Substring Without Repeating Characters“?

Beide bewegen sich um zwei Kanten über den String, aber die Regel für ein gültiges Fenster ist unterschiedlich. Dort ist ein Fenster gültig, wenn kein Zeichen wiederholt wird, und es muss verkleinert werden, bis es keine Wiederholung mehr gibt. Hier ist ein Fenster gültig, wenn seine Länge minus der Häufigkeit seines am häufigsten vorkommenden Buchstabens höchstens k beträgt. Dadurch kann das Fenster bei fester Länge weitergleiten, anstatt verkleinert zu werden.

Kann dieses Problem mit binärer Suche gelöst werden?

Ja. Wenn ein Teilstring der Länge L erreichbar ist, ist auch jeder kürzere Teilstring darin erreichbar, sodass du eine binäre Suche über L durchführen kannst. Schiebe für jedes L ein Fenster fester Länge darüber und prüfe, ob an einer Position höchstens k Änderungen erforderlich sind. Das ist O(n log n), langsamer als die Lösung mit einem Fenster, aber eine durchaus vertretbare Antwort.

Python

def characterReplacement(s, k):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "BAAACAB"
k = 1

Erwartet

Longest Repeating Character Replacement

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Jeden Teilstring überprüfen

Ein gleitendes Fenster pro Zielbuchstabe

Ein Fenster, das nie kleiner wird

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben