Longest Repeating Character Replacement

+10

Hai una stringa s composta da lettere maiuscole inglesi e un intero k. Puoi scegliere al massimo k posizioni di s e cambiare la lettera in ciascuna di esse con un'altra lettera maiuscola.

Restituisci la lunghezza della sottostringa più lunga, cioè una sequenza di lettere consecutive, che contiene una sola lettera ripetuta dopo le modifiche.

Funzione

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

sstring: la stringa di lettere maiuscole
kinteger: il maggior numero di lettere che puoi modificare
Restituisceinteger: la lunghezza della sottostringa più lunga che puoi ottenere ripetendo una sola lettera

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo lettere maiuscole inglesi.
0 ≤ k ≤ s.length

Esempi

Input: s = "BAAACAB"k = 1
Output: 5
Spiegazione: Cambiare la C in A fa sì che gli indici da 1 a 5 contengano AAAAA. Entrambe le finestre di sei lettere contengono una B e la C, quindi richiedono due modifiche.

Input: s = "AABBBAB"k = 2
Output: 6
Spiegazione: Gli indici da 1 a 6 contengono ABBBAB e, cambiando entrambe le lettere A, si ottiene BBBBBB. L'intera stringa contiene solo quattro lettere B su sette, quindi servono tre modifiche.

Per approfondire

Che cosa cambia se s può contenere qualsiasi carattere anziché le 26 lettere maiuscole?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Mantieni la lettera più frequente di una sottostringa e cambia le altre: una sottostringa di lunghezza len la cui lettera più frequente compare top volte richiede len - top modifiche. Una finestra scorrevole trova la sottostringa più lunga con len - top ≤ k in un solo passaggio, perché non è mai necessario restringere la finestra e top non deve mai diminuire.

Controlla ogni sottostringa

Corretto, ma non termina sui test più grandi

Intuizione

Per ogni inizio, allunga la fine di una lettera alla volta, aggiorna il conteggio per ogni lettera e top, e verifica len - top ≤ k. Ogni nuova sottostringa richiede un aggiornamento invece di un nuovo conteggio, e ogni sottostringa viene verificata, quindi non si può perdere quella più lunga raggiungibile.

Una stringa di lunghezza n ha circa n²/2 sottostringhe: 1.25 × 10^9 verifiche per n = 5 × 10^4.

Algoritmo

Imposta best a 0.
Per ogni indice iniziale, azzera i 26 conteggi e top a 0.
Sposta end dall'inizio fino all'ultimo indice. Aggiungi s[end] al suo conteggio e aumenta top se quel conteggio è ora il più alto.
Se end - start + 1 - top ≤ k, memorizza la lunghezza se supera best.
Restituisci best.

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

Una finestra scorrevole per ogni lettera di destinazione

Intuizione

Scegli prima la lettera finale. Se alla fine la sequenza è tutta A, vuoi la sottostringa più lunga con al massimo k lettere diverse da A.

Sposta right lungo la stringa e conta le lettere diverse da quella scelta nella finestra. Quando il conteggio supera k, sposta left in avanti finché non torna a k. Una finestra troppo costosa resta troppo costosa quando si allunga, quindi left non si sposta mai indietro e, per ogni right, la finestra è la più lunga possibile che termina lì.

Esegui l’algoritmo per tutte e 26 le lettere e conserva il risultato migliore: 26 passaggi lineari su un massimo di 5 × 10^4 lettere. Rimane O(n) solo perché l’alfabeto è piccolo.

Algoritmo

Per ogni lettera obiettivo da A a Z, avvia una finestra con left = 0 e others = 0.
Sposta right lungo la stringa. Se s[right] non è l'obiettivo, incrementa others di uno.
Mentre others > k, sposta left in avanti, sottraendo uno quando la lettera che esce non è l'obiettivo.
Memorizza right - left + 1 se supera best.
Dopo tutte e 26 le lettere, restituisci best.

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

Una finestra che non si restringe mai

Intuizione

Mantieni i conteggi delle 26 lettere per la finestra e top, il conteggio più alto. Quando aggiungere s[right] rende la finestra troppo costosa, elimina una lettera a sinistra: la finestra scorre e mantiene la sua lunghezza, poiché solo una finestra più lunga può battere il record. Altrimenti cresce di uno. La sua lunghezza è sempre la migliore finora, quindi la risposta è n - left.

Quando una lettera esce, lascia invariato top, anche se ora è più alto del conteggio effettivo. Dopo uno scorrimento, la lunghezza è esattamente top + k, quindi per crescere è necessario che qualche lettera compaia top + 1 volte, e in quel momento anche top aumenta. Un top non aggiornato può solo far scorrere la finestra, e uno scorrimento non può far perdere il record.

In BAAACAB con k = 1, BAAAC richiede 2 modifiche e scorre fino a AAAC. La A successiva porta top a 4 e la finestra cresce fino a AAACA, lunghezza 5.

Algoritmo

Mantieni 26 conteggi, left = 0 e top = 0.
Fai avanzare right lungo la stringa: aggiungi s[right] al relativo conteggio e aumenta top se quel conteggio è ora più alto.
Se right - left + 1 - top > k, rimuovi s[left] dai conteggi e sposta left di un passo. Non diminuire mai top.
Restituisci la lunghezza finale della finestra, 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

Trappole e casi limite

Aggiungere k alla serie più lunga. In AAAB con k = 3 si ottiene 6, più della lunghezza della stringa. In BAAACAB con k = 1 si ottiene 4, ma modificando la C si uniscono due serie e si ottiene 5.
Contare le modifiche rispetto alla prima lettera della finestra invece che a quella più frequente. BAAA richiede una modifica, non tre.
Restituire n - left da un ciclo che restringe la finestra con while e ricalcola il massimo effettivo. La finestra si accorcia, quindi tieni un best separato.
Misurare la finestra come right - left. Entrambe le estremità sono al suo interno, quindi aggiungi uno.

Domande frequenti3

Qual è la complessità temporale della sostituzione del carattere ripetuto più lungo?

La soluzione a finestra singola richiede un tempo O(n), dove n è la lunghezza di s: right visita ogni lettera una volta e left si sposta al massimo una volta per passaggio. Usa O(1) spazio aggiuntivo, 26 conteggi e pochi numeri interi.

In che cosa è diverso da Longest Substring Without Repeating Characters?

Entrambi spostano due estremi sulla stringa, ma la regola per una finestra valida è diversa. In quel caso, nessun carattere può ripetersi, quindi la finestra si restringe finché la ripetizione non scompare. Qui, la lunghezza meno il conteggio massimo deve essere al massimo k, quindi la finestra può scorrere mantenendo una lunghezza fissa.

Questo problema può essere risolto con la ricerca binaria?

Sì. Se è raggiungibile una sottostringa di lunghezza L, lo è anche ogni sottostringa più corta al suo interno, quindi puoi eseguire una ricerca binaria su L. Per ogni L, fai scorrere una finestra fissa di quella lunghezza e controlla se esiste una posizione che richiede al massimo k modifiche. È O(n log n), più lento della soluzione con una sola finestra.

def characterReplacement(s, k):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

s = "BAAACAB"
k = 1

Output atteso

Longest Repeating Character Replacement

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni sottostringa

Una finestra scorrevole per ogni lettera di destinazione

Una finestra che non si restringe mai

Trappole e casi limite

Domande frequenti3

Problemi simili