Longest Repeating Character Replacement

+10

Você recebe uma string s de letras maiúsculas do alfabeto inglês e um inteiro k. Você pode escolher no máximo k posições de s e alterar a letra em cada uma delas para qualquer outra letra maiúscula.

Retorne o comprimento da substring mais longa — uma sequência de letras adjacentes — que contenha uma única letra repetida após suas alterações.

Função

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

sstring: a sequência de letras maiúsculas
kinteger: o maior número de letras que você pode alterar
Retornainteger: o comprimento da maior substring de uma letra repetida que você consegue formar

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras maiúsculas do alfabeto inglês.
0 ≤ k ≤ s.length

Exemplos

Entrada: s = "BAAACAB"k = 1
Saída: 5
Explicação: Troque o C por um A e os índices de 1 a 5 formam AAAAA. Para seis letras, seriam necessárias duas alterações: os índices de 0 a 5 contêm um B e o C, e os índices de 1 a 6 contêm o C e o último B.

Entrada: s = "AABBBAB"k = 2
Saída: 6
Explicação: Em ABBBAB, nos índices de 1 a 6, os dois As são as únicas letras que não são B, então duas alterações resultam em BBBBBB. A string inteira contém três As e quatro Bs, então precisa de três alterações.

+17 testes ocultos ao enviar

Para ir além

O que muda se s puder conter qualquer caractere, e não apenas as 26 letras maiúsculas?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

O custo de uma substring é fácil de ver: seu comprimento menos a contagem da letra mais comum nela. A parte difícil é não calcular o custo de todas as n² substrings. Uma janela deslizante percorre a string uma vez, e a melhor versão se baseia em dois fatos: a janela nunca precisa encolher, e a maior contagem de letras nunca precisa diminuir.

Verifique cada substring

Correta, mas não termina nos maiores testes

Intuição

Corrija uma substring. Em qual letra ela deve se transformar? Na que já aparece com mais frequência, porque todas as outras letras precisam mudar. Portanto, uma substring de comprimento len cuja letra mais frequente aparece top vezes precisa de len - top alterações, e é possível transformá-la quando esse valor é menor ou igual a k.

Experimente todas as substrings. Para cada posição inicial, aumente o final uma letra por vez e mantenha uma contagem por letra, atualizando top à medida que avança. Assim, cada nova substring exige apenas uma atualização, em vez de uma nova contagem do zero. Todas as substrings são verificadas, então não é possível deixar passar a maior que pode ser transformada.

Isso é lento porque uma string de comprimento n tem cerca de n²/2 substrings. Para n = 5 × 10^4, são 1.25 × 10^9 verificações, muito mais do que o limite de tempo permite.

Algoritmo

Defina best como 0.
Para cada índice inicial, redefina as 26 contagens e top como 0.
Mova end do início até o último índice. Adicione s[end] à sua contagem e aumente top se essa contagem agora for a mais alta.
Se end - start + 1 - top ≤ k, a substring pode ser obtida: armazene seu comprimento se ele superar best.
Retorne 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

Uma janela deslizante para cada letra-alvo

Intuição

Inverta a pergunta e escolha primeiro a letra. Se a sequência final for toda A, a pergunta passa a ser: qual é a substring mais longa com no máximo k letras que não são A? Esse é um exemplo clássico de janela deslizante.

Percorra a string com right e conte as letras dentro da janela que não são o alvo. Quando essa contagem ultrapassar k, avance left até que ela volte a ser k. Aumentar uma janela só pode acrescentar letras a serem alteradas, então uma janela que custa caro demais continua custando caro demais quando cresce, e left nunca precisa voltar. Para cada right, a janela mantida é a maior janela válida que termina ali.

Execute isso para todas as 26 letras e mantenha o melhor comprimento. Cada execução leva O(n), então são 26 passagens, cerca de 1.3 × 10^6 etapas para n = 5 × 10^4. Isso é linear, mas lê a string 26 vezes e só funciona porque o alfabeto é pequeno.

Algoritmo

Para cada letra-alvo de A a Z, inicie uma janela com left = 0 e others = 0.
Mova right pela string. Se s[right] não for a letra-alvo, some um a others.
Enquanto others > k, avance left e subtraia um de others quando a letra que sai não for a letra-alvo.
Armazene right - left + 1 se esse valor superar best.
Depois de considerar todas as 26 letras, retorne 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

Uma janela que nunca encolhe

Intuição

Considere cada letra em uma janela. Mantenha a contagem de cada uma das 26 letras dentro dela e top, a maior contagem. A janela precisa de length - top alterações, então ela é válida quando esse valor é, no máximo, k.

Primeiro fato: a janela nunca precisa encolher. Você só precisa superar o melhor comprimento encontrado até então; por isso, quando adicionar s[right] tornar a janela cara demais, remova uma letra à esquerda. A janela desliza um passo e mantém o mesmo comprimento. Quando a janela não é cara demais, ela cresce em uma unidade. Portanto, seu comprimento é sempre o melhor comprimento encontrado até então e, no final, a resposta é n - left.

Segundo fato: top nunca precisa diminuir. Quando uma letra sai pela esquerda, você mantém top como está, então ele pode ser maior que a contagem real dentro da janela. Isso é seguro. Depois de um deslizamento, o comprimento da janela é exatamente top + k; portanto, para crescer, ela precisa de uma letra que apareça top + 1 vezes dentro da janela e, nesse momento, top aumenta junto. Um top desatualizado pode fazer a janela deslizar, mas nunca crescer por engano; e deslizar não causa perdas, porque apenas uma janela mais longa poderia superar o recorde.

Em BAAACAB com k = 1, a janela cresce até BAAA e, então, BAAAC precisa de 2 alterações, por isso ela desliza para AAAC. Adicionar o próximo A eleva top para 4 e a janela cresce até AAACA, com comprimento 5. O último B faz a janela deslizar mais uma vez, então a resposta é 5.

Algoritmo

Mantenha as contagens das 26 letras, left = 0 e top = 0.
Mova right pela string: some s[right] à sua contagem e aumente top se essa contagem ficar maior.
Se right - left + 1 - top > k, a janela precisa de alterações demais: remova s[left] das contagens e mova left uma posição. A janela desliza e mantém seu comprimento.
Nunca diminua top quando uma letra sair.
Retorne o comprimento final da janela, 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

Armadilhas e casos extremos

O código da janela é curto, então a maioria das respostas erradas vem da fórmula de custo ou de um atalho que só parece correto.

Somar k à sequência mais longa. Em AAAB com k = 3, isso resulta em 6, mais do que o tamanho da string. Em BAAACAB com k = 1, resulta em 4, mas a alteração correta fica no meio e une duas sequências, formando uma de 5.
Contar as alterações em relação à primeira letra da janela, em vez da letra mais comum. A janela BAAA precisa de uma alteração, não de três.
Retornar n - left em uma versão cuja janela pode encolher. Esse atalho só funciona quando a janela nunca fica menor, como no código de janela única aqui. Se o seu loop encolhe a janela com while e recalcula o máximo real, mantenha um best separado.
Medir a janela como right - left. As duas extremidades estão dentro dela, então some um.
Tratar k = 0 como um caso especial. Sem alterações, a regra da janela já retorna a sequência mais longa de uma letra.

Perguntas frequentes4

Qual é a complexidade de tempo de Longest Repeating Character Replacement?

A solução de janela única é executada em tempo O(n), em que n é o comprimento de s: right visita cada letra uma vez e left se move no máximo uma vez por etapa. Ela usa espaço extra O(1), 26 contagens e alguns números inteiros.

Por que a frequência máxima não precisa ser atualizada quando a janela desliza?

A janela está apenas tentando superar seu próprio recorde. Depois de um deslizamento, seu comprimento é top + k, então uma janela válida mais longa precisa que alguma letra apareça mais de top vezes, o que aumenta top de qualquer maneira. Um top alto demais apenas mantém a janela no mesmo comprimento; ele nunca faz com que ela cresça quando não deveria.

Em que isso difere de Longest Substring Without Repeating Characters?

Ambos percorrem duas extremidades da string, mas a regra para uma janela válida é diferente. Lá, uma janela é válida quando nenhum caractere se repete, e ela precisa diminuir até que a repetição desapareça. Aqui, uma janela é válida quando seu comprimento menos a contagem da letra mais frequente é no máximo k, o que permite que a janela deslize em um comprimento fixo, em vez de diminuir.

Este problema pode ser resolvido com busca binária?

Sim. Se uma substring de comprimento L é alcançável, então todas as substrings menores contidas nela também são, portanto você pode fazer uma busca binária em L. Para cada L, deslize uma janela fixa desse comprimento e verifique se alguma posição precisa de, no máximo, k alterações. Isso é O(n log n), mais lento que a solução com uma única janela, mas é uma resposta razoável.

Python

def characterReplacement(s, k):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "BAAACAB"
k = 1

Esperado

Longest Repeating Character Replacement

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada substring

Uma janela deslizante para cada letra-alvo

Uma janela que nunca encolhe

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos