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 davon in einen beliebigen anderen Großbuchstaben ändern.

Gib die Länge der längsten Teilzeichenfolge zurück, einer Folge von direkt aufeinanderfolgenden Buchstaben, die nach deinen Änderungen nur einen einzigen wiederholten Buchstaben enthält.

Funktion

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

sstring: die Zeichenfolge aus Großbuchstaben
kinteger: die meisten Buchstaben, die du ändern darfst
Gibt zurückinteger: die Länge der längsten Teilzeichenfolge, die du aus Wiederholungen eines einzelnen Buchstabens bilden kannst

Einschränkungen

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

Beispiele

Eingabe: s = "BAAACAB"k = 1
Ausgabe: 5
Erklärung: Wenn du das C in A änderst, lesen sich die Indizes 1 bis 5 als AAAAA. Beide Sechs-Zeichen-Fenster enthalten ein B und das C, daher sind zwei Änderungen nötig.

Eingabe: s = "AABBBAB"k = 2
Ausgabe: 6
Erklärung: Die Indizes 1 bis 6 enthalten ABBBAB, und wenn du beide A-Buchstaben änderst, erhältst du BBBBBB. Die gesamte Zeichenfolge enthält nur vier B-Buchstaben unter sieben, daher sind drei Änderungen nötig.

Weiterführende Frage

Was ändert sich, wenn s ein beliebiges Zeichen statt eines der 26 Großbuchstaben enthalten kann?

Tipps

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

0 von 3 geöffnet

Lösung

Behalte den häufigsten Buchstaben einer Teilzeichenfolge bei und ändere den Rest: Eine Teilzeichenfolge der Länge len, in der der häufigste Buchstabe top Mal vorkommt, benötigt len - top Änderungen. Mit einem gleitenden Fenster lässt sich in einem Durchgang die längste Teilzeichenfolge mit len - top ≤ k finden, da das Fenster nie verkleinert werden muss und top nie kleiner werden muss.

Prüfe jede Teilzeichenfolge

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

Idee

Vergrößere für jeden Start das Ende jeweils um einen Buchstaben, aktualisiere eine Anzahl pro Buchstabe und top und prüfe len - top ≤ k. Für jeden neuen Teilstring ist nur eine Aktualisierung statt einer neuen Zählung nötig, und da jeder Teilstring geprüft wird, kann der längste erreichbare nicht übersehen werden.

Ein String der Länge n hat ungefähr n²/2 Teilstrings: 1.25 × 10^9 Prüfungen für n = 5 × 10^4.

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. Erhöhe den Zähler für s[end] und erhöhe top, wenn dieser Zähler nun den höchsten Wert hat.
Wenn end - start + 1 - top ≤ k, speichere die 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

Wähle zuerst den endgültigen Buchstaben. Wenn die Folge am Ende nur aus A besteht, suchst du die längste Teilzeichenfolge mit höchstens k Buchstaben, die nicht A sind.

Bewege right über die Zeichenfolge und zähle die Buchstaben im Fenster, die nicht dem Zielbuchstaben entsprechen. Wenn die Anzahl k überschreitet, bewege left nach vorne, bis sie wieder k beträgt. Ein Fenster, das zu viele Änderungen erfordert, bleibt auch dann zu aufwendig, wenn es wächst. Daher bewegt sich left nie zurück, und für jedes right ist das Fenster das längste gültige Fenster, das dort endet.

Führe das für alle 26 Buchstaben aus und behalte das beste Ergebnis: 26 lineare Durchläufe über bis zu 5 × 10^4 Buchstaben. Es bleibt nur deshalb bei O(n), weil das Alphabet klein ist.

Algorithmus

Starte für jeden Zi buchstaben von A bis Z ein Fenster mit left = 0 und others = 0.
Bewege right über den String. Wenn s[right] nicht der Zielbuchstabe ist, erhöhe others um eins.
Solange others > k gilt, bewege left nach vorne und ziehe eins ab, wenn der Buchstabe, der das Fenster verlässt, nicht der Zielbuchstabe 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 niemals schrumpft

Idee

Halte 26 Zähler für das Fenster und top, den höchsten Zähler, bereit. Wenn s[right] das Fenster zu teuer macht, entferne links einen Buchstaben: Das Fenster verschiebt sich und behält seine Länge bei, denn nur ein längeres Fenster kann den Rekord übertreffen. Andernfalls wächst es um eins. Seine Länge ist immer die bisher beste, also lautet die Antwort n - left.

Wenn ein Buchstabe das Fenster verlässt, lass top unverändert, auch wenn der Wert nun höher ist als der tatsächliche Zähler. Nach einer Verschiebung ist die Länge genau top + k. Damit das Fenster wachsen kann, muss also ein Buchstabe top + 1-mal vorkommen, und top steigt in diesem Moment mit. Ein veralteter Wert von top kann das Fenster nur zum Verschieben bringen, und dadurch kann der Rekord nicht verloren gehen.

Bei BAAACAB mit k = 1 erfordert BAAAC 2 Änderungen und verschiebt sich zu AAAC. Das nächste A erhöht top auf 4, und das Fenster wächst zu AAACA mit Länge 5.

Algorithmus

Behalte 26 Zähler, left = 0 und top = 0.
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, entferne s[left] aus den Zählern und bewege left um einen Schritt weiter. Verringere top niemals.
Gib die endgültige Fensterlänge 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

k zum längsten Lauf addieren. Bei AAAB ergibt das mit k = 3 den Wert 6, der länger als die Zeichenkette ist. Bei BAAACAB ergibt das mit k = 1 den Wert 4, aber durch das Ändern von C werden zwei Läufe zu einem Lauf der Länge 5 verbunden.
Änderungen anhand des ersten Buchstabens des Fensters statt anhand seines häufigsten Buchstabens zählen. BAAA benötigt eine Änderung, nicht drei.
Aus einer Schleife, die das Fenster mit while verkleinert und das tatsächliche Maximum neu berechnet, n - left zurückgeben. Dieses Fenster wird kürzer, daher solltest du ein separates best beibehalten.
Das Fenster als right - left messen. Beide Enden liegen innerhalb des Fensters, also addiere eins.

Häufige Fragen3

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

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

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

Beide bewegen zwei Grenzen über den String, aber die Regel für ein gültiges Fenster ist unterschiedlich. Dort darf kein Zeichen mehrfach vorkommen, also wird das Fenster verkleinert, bis das Zeichen nicht mehr doppelt vorkommt. Hier muss die Länge minus der höchsten Häufigkeit höchstens k betragen, sodass das Fenster mit fester Länge verschoben werden kann.

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 für L eine binäre Suche durchführen kannst. Schiebe für jedes L ein festes Fenster dieser Länge entlang und prüfe, ob an einer Position höchstens k Änderungen nötig sind. Das ist O(n log n) und damit langsamer als die Lösung mit einem Fenster.

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

Test #1

Test #2

Test #3

Argumente

s = "BAAACAB"
k = 1

Erwartete Ausgabe

Longest Repeating Character Replacement

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Prüfe jede Teilzeichenfolge

Ein gleitendes Fenster pro Zielbuchstabe

Ein Fenster, das niemals schrumpft

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben