Longest Repeating Character Replacement

+10

Você recebe uma string s formada por letras maiúsculas do alfabeto inglês e um inteiro k. Você pode escolher no máximo k posições de s e trocar a letra em cada uma delas por 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 as alterações.

Função

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

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

Restrições

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

Exemplos

Entrada: s = "BAAACAB"k = 1
Saída: 5
Explicação: Alterar o C para A faz com que os índices de 1 a 5 formem AAAAA. As duas janelas de seis letras contêm um B e o C, então precisam de duas alterações.

Entrada: s = "AABBBAB"k = 2
Saída: 6
Explicação: Os índices de 1 a 6 contêm ABBBAB, e alterar as duas letras A resulta em BBBBBB. A string inteira tem apenas quatro letras B entre sete, então precisa de três alterações.

Para ir além

O que muda se s puder conter qualquer caractere em vez das 26 letras maiúsculas?

Dicas

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

0 de 3 abertas

Solução

Mantenha a letra mais frequente de uma substring e altere as demais: uma substring de comprimento len cuja letra mais frequente aparece top vezes precisa de len - top alterações. Uma janela deslizante encontra a substring mais longa com len - top ≤ k em uma única passagem, porque a janela nunca precisa diminuir e top nunca precisa diminuir.

Verifique cada substring

Correta, mas não termina nos maiores testes

Intuição

Para cada início, aumente o fim uma letra por vez, atualize uma contagem por letra e top, e teste len - top ≤ k. Cada nova substring custa uma atualização em vez de uma nova contagem, e todas as substrings são verificadas, então a mais longa que pode ser alcançada não será ignorada.

Uma string de comprimento n tem cerca de n²/2 substrings: 1,25 × 10^9 verificações para n = 5 × 10^4.

Algoritmo

Defina best como 0.
Para cada índice inicial, redefina as 26 contagens e top como 0.
Mova end do índice inicial 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, armazene o 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 por letra-alvo

Intuição

Escolha primeiro a letra final. Se a sequência acabar sendo toda A, você quer a substring mais longa com no máximo k letras que não sejam A.

Percorra a string com right e conte as letras que não são o alvo na janela. Quando a contagem passar de k, avance left até voltar a k. Uma janela que custa demais continua custando demais quando cresce, então left nunca retrocede e, para cada right, a janela é a mais longa válida que termina ali.

Execute isso para todas as 26 letras e mantenha o melhor resultado: 26 percursos lineares por até 5 × 10^4 letras. Isso só permanece O(n) porque o alfabeto é pequeno.

Algoritmo

Para cada letra-alvo de A a Z, inicie uma janela com left = 0 e others = 0.
Percorra a string com right. Se s[right] não for a letra-alvo, incremente others em um.
Enquanto others > k, avance left, subtraindo um quando a letra que sai não for a letra-alvo.
Armazene right - left + 1 se esse valor superar best.
Depois de 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

Mantenha 26 contagens para a janela e top, a contagem mais alta. Quando adicionar s[right] tornar a janela cara demais, remova uma letra da esquerda: a janela desliza e mantém seu comprimento, pois somente uma janela mais longa pode superar o recorde. Caso contrário, ela cresce em um. Seu comprimento é sempre o melhor até agora, então a resposta é n - left.

Quando uma letra sai, não altere top, mesmo que agora ele seja maior que a contagem real. Após um deslizamento, o comprimento é exatamente top + k, então, para crescer, alguma letra precisa aparecer top + 1 vezes, e top aumenta nesse momento. Um top desatualizado só pode fazer a janela deslizar, e um deslizamento não pode perder o recorde.

Em BAAACAB com k = 1, BAAAC precisa de 2 alterações e desliza para AAAC. O próximo A eleva top para 4 e a janela cresce para AAACA, com comprimento 5.

Algoritmo

Mantenha 26 contagens, left = 0 e top = 0.
Mova right pela string: adicione s[right] à sua contagem e aumente top se essa contagem ficar maior.
Se right - left + 1 - top > k, remova s[left] das contagens e mova left uma posição. Nunca diminua top.
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

Adicionar k à sequência mais longa. Em AAAB com k = 3, isso resulta em 6, maior que o tamanho da string. Em BAAACAB com k = 1, resulta em 4, mas alterar o C une duas sequências, formando uma de 5.
Contar as alterações em relação à primeira letra da janela, em vez da mais frequente. BAAA precisa de uma alteração, não de três.
Retornar n - left de um loop que reduz a janela com while e recalcula o máximo real. Essa janela fica menor, então mantenha um best separado.
Medir a janela como right - left. As duas extremidades estão dentro dela, então some um.

Perguntas frequentes3

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.

Em que isso é diferente de Longest Substring Without Repeating Characters?

Ambos deslocam duas extremidades ao longo da string, mas a regra para uma janela válida é diferente. Lá, nenhum caractere pode se repetir, então a janela diminui até que a repetição desapareça. Aqui, o comprimento menos a contagem máxima deve ser no máximo k, então a janela pode deslizar mantendo um comprimento fixo.

Este problema pode ser resolvido com busca binária?

Sim. Se uma substring de comprimento L é alcançável, todas as substrings menores contidas nela também são, então 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 do que a solução de janela única.

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

Teste #1

Teste #2

Teste #3

Argumentos

s = "BAAACAB"
k = 1

Saída Esperada

Longest Repeating Character Replacement

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada substring

Uma janela deslizante por letra-alvo

Uma janela que nunca encolhe

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos