Longest Repeating Character Replacement

+10

Ti viene fornita 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 qualsiasi altra lettera maiuscola.

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

Funzione

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

sstring: la stringa di lettere maiuscole
kinteger: il maggior numero di lettere che puoi cambiare
Restituisceinteger: la lunghezza della sottostringa più lunga di una lettera ripetuta che puoi creare

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: Sostituisci la C con una A e gli indici da 1 a 5 contengono AAAAA. Per sei lettere servirebbero due modifiche: gli indici da 0 a 5 contengono una B e la C, mentre gli indici da 1 a 6 contengono la C e l’ultima B.

Input: s = "AABBBAB"k = 2
Output: 6
Spiegazione: In ABBBAB, gli indici da 1 a 6, le due A sono le sole lettere che non sono B, quindi due modifiche danno BBBBBB. L’intera stringa contiene tre A e quattro B, quindi servono tre modifiche.

+17 test nascosti all’invio

Per approfondire

Che cosa cambia se s può contenere qualsiasi carattere, non solo le 26 lettere maiuscole?

Suggerimenti

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

0 di 3 aperti

Soluzione

Il costo di una sottostringa è facile da vedere: la sua lunghezza meno il conteggio della lettera più frequente. La parte difficile è non dover pagare per tutte le n² sottostringhe. Una finestra scorrevole legge la stringa una sola volta e la versione migliore si basa su due fatti: la finestra non deve mai restringersi e il conteggio della lettera più frequente non deve mai diminuire.

Controlla ogni sottostringa

Corretto, ma non termina sui test più grandi

Intuizione

Sistema una sottostringa. In quale lettera dovrebbe diventare? Quella che è già presente più spesso, perché tutte le altre lettere devono cambiare. Quindi una sottostringa di lunghezza len la cui lettera più frequente compare top volte richiede len - top modifiche, ed è raggiungibile quando tale valore è al massimo k.

Prova ogni sottostringa. Per ogni posizione iniziale, allunga la posizione finale di una lettera alla volta e mantieni un conteggio per ogni lettera, aumentando top man mano. Ogni nuova sottostringa richiede così un solo aggiornamento invece di un conteggio da zero. Vengono controllate tutte le sottostringhe, quindi non puoi perdere quella raggiungibile più lunga.

È lento perché una stringa di lunghezza n ha circa n²/2 sottostringhe. Per n = 5 × 10^4 si tratta di 1.25 × 10^9 controlli, molti più di quelli consentiti dal limite di tempo.

Algoritmo

Imposta best a 0.
Per ogni indice iniziale, azzera i 26 conteggi e top a 0.
Sposta end dall'inizio 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, la sottostringa è raggiungibile: memorizza la sua 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 obiettivo

Intuizione

Riformula la domanda e scegli prima la lettera. Se la sequenza finale è tutta A, la domanda diventa: qual è la sottostringa più lunga con al massimo k lettere diverse da A? È un classico caso di finestra scorrevole.

Sposta right lungo la stringa e conta le lettere nella finestra che non sono quella scelta. Quando il conteggio supera k, sposta left in avanti finché non torna a k. Allargare una finestra può solo aggiungere lettere da modificare, quindi una finestra troppo costosa resta tale anche quando si allarga e left non deve mai tornare indietro. Per ogni right, la finestra mantenuta è la più lunga tra quelle valide che terminano lì.

Esegui questa operazione per tutte le 26 lettere e tieni la lunghezza migliore. Ogni esecuzione richiede O(n), quindi in totale sono 26 passaggi, circa 1.3 × 10^6 operazioni per n = 5 × 10^4. È un algoritmo lineare, ma legge la stringa 26 volte e funziona 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 è la lettera obiettivo, incrementa others di uno.
Finché others > k, sposta left in avanti e decrementa others di uno quando la lettera che esce non è la lettera obiettivo.
Memorizza right - left + 1 se supera best.
Dopo aver esaminato tutte le 26 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

Considera ogni lettera in una finestra. Tieni il conteggio di ciascuna delle 26 lettere al suo interno e top, il conteggio più alto. Per la finestra servono length - top modifiche, quindi va bene quando questo valore è al massimo k.

Primo fatto: la finestra non deve mai restringersi. Ti interessa solo superare la lunghezza migliore trovata finora, quindi quando aggiungere s[right] rende la finestra troppo costosa, rimuovi una lettera da sinistra. La finestra scorre di un passo e mantiene la stessa lunghezza. Quando la finestra non è troppo costosa, cresce di uno. La sua lunghezza è quindi sempre la migliore trovata finora e, alla fine, la risposta è n - left.

Secondo fatto: top non deve mai diminuire. Quando una lettera esce da sinistra, lasci invariato top, quindi può essere maggiore del conteggio reale all'interno della finestra. È sicuro. Dopo uno scorrimento, la lunghezza della finestra è esattamente top + k, quindi per farla crescere serve una lettera che compaia top + 1 volte all'interno della finestra e, in quel momento, anche top aumenta. Un valore non aggiornato di top può far scorrere la finestra, ma non farla crescere per errore; e lo scorrimento non fa perdere nulla, perché solo una finestra più lunga potrebbe superare il record.

In BAAACAB con k = 1, la finestra cresce fino a BAAA e poi BAAAC richiede 2 modifiche, quindi scorre fino a AAAC. Aggiungendo la A successiva, top aumenta a 4 e la finestra cresce fino a AAACA, lunghezza 5. L'ultima B la fa scorrere ancora una volta, quindi la risposta è 5.

Algoritmo

Mantieni 26 conteggi, left = 0 e top = 0.
Sposta right lungo la stringa: aggiungi s[right] al suo conteggio e aumenta top se quel conteggio è ora più alto.
Se right - left + 1 - top > k, la finestra richiede troppe modifiche: rimuovi s[left] dai conteggi e sposta left di un passo. La finestra scorre e mantiene la sua lunghezza.
Non abbassare mai top quando una lettera esce.
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

Il codice della finestra è breve, quindi la maggior parte delle risposte errate deriva dalla formula del costo o da una scorciatoia che sembra corretta solo in apparenza.

Aggiungere k alla sequenza più lunga. In AAAB con k = 3 si ottiene 6, un valore superiore alla lunghezza della stringa. In BAAACAB con k = 1 si ottiene 4, ma la modifica corretta si trova in mezzo e unisce due sequenze, ottenendo 5.
Contare le modifiche rispetto alla prima lettera della finestra invece che alla lettera più frequente. La finestra BAAA richiede una modifica, non tre.
Restituire n - left in una versione in cui la finestra può restringersi. Questa scorciatoia funziona solo quando la finestra non si accorcia mai, come nel codice con una sola finestra qui. Se il tuo ciclo restringe la finestra con while e ricalcola il massimo effettivo, mantieni un best separato.
Calcolare la lunghezza della finestra come right - left. Entrambi gli estremi sono inclusi, quindi aggiungi uno.
Trattare k = 0 come un caso speciale. Senza modifiche, la regola della finestra restituisce già la sequenza più lunga composta da una sola lettera.

Domande frequenti4

Qual è la complessità temporale di Longest Repeating Character Replacement?

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 uno spazio aggiuntivo O(1), 26 conteggi e pochi numeri interi.

Perché non è necessario aggiornare la frequenza massima quando la finestra scorre?

La finestra sta solo cercando di battere il proprio record. Dopo uno scorrimento, la sua lunghezza è top + k, quindi una finestra valida più lunga richiede che qualche lettera compaia più di top volte, e questo aumenta comunque top. Un valore di top troppo alto mantiene solo la finestra alla sua lunghezza; non la fa mai crescere quando non dovrebbe.

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

Entrambi spostano due estremi lungo la stringa, ma la regola per una finestra valida è diversa. In quel caso, una finestra è valida quando nessun carattere si ripete e deve restringersi finché la ripetizione non scompare. Qui, una finestra è valida quando la sua lunghezza meno il conteggio della lettera più frequente è al massimo k, il che consente alla finestra di scorrere mantenendo una lunghezza fissa invece di restringersi.

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. Questo è O(n log n), più lento della soluzione con una sola finestra, ma è una risposta ragionevole da dare.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "BAAACAB"
k = 1

Atteso

Longest Repeating Character Replacement

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni sottostringa

Una finestra scorrevole per ogni lettera obiettivo

Una finestra che non si restringe mai

Trappole e casi limite

Domande frequenti4

Problemi simili