Longest Repeating Character Replacement

+10

Recibes una cadena s de letras mayúsculas del inglés y un entero k. Puedes elegir como máximo k posiciones de s y cambiar la letra de cada una por cualquier otra letra mayúscula.

Devuelve la longitud de la subcadena más larga, una secuencia de letras contiguas, que contiene una sola letra repetida después de tus cambios.

Función

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

sstring: la cadena de letras mayúsculas
kinteger: la mayor cantidad de letras que puedes cambiar
Devuelveinteger: la longitud de la subcadena más larga que puedes formar con una letra repetida

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene únicamente letras inglesas mayúsculas.
0 ≤ k ≤ s.length

Ejemplos

Entrada: s = "BAAACAB"k = 1
Salida: 5
Explicación: Cambiar la C por A hace que los índices del 1 al 5 muestren AAAAA. Ambas ventanas de seis letras contienen una B y la C, así que necesitan dos cambios.

Entrada: s = "AABBBAB"k = 2
Salida: 6
Explicación: Los índices del 1 al 6 contienen ABBBAB, y cambiar ambas letras A da como resultado BBBBBB. La cadena completa solo tiene cuatro letras B de un total de siete, así que necesita tres cambios.

Para ir más allá

¿Qué cambia si s puede contener cualquier carácter en lugar de las 26 letras mayúsculas?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Conserva la letra más frecuente de una subcadena y cambia el resto: una subcadena de longitud len cuya letra más frecuente aparece top veces necesita len - top cambios. Una ventana deslizante encuentra la subcadena más larga con len - top ≤ k en una sola pasada, porque la ventana nunca necesita encogerse y top nunca tiene que disminuir.

Comprueba cada subcadena

Correcto, pero no termina con las pruebas más grandes

Intuición

Para cada inicio, amplía el final una letra a la vez, actualiza un recuento por letra y top, y comprueba len - top ≤ k. Cada nueva subcadena requiere una actualización en lugar de un recuento desde cero, y se comprueban todas las subcadenas, así que no se puede pasar por alto la más larga alcanzable.

Una cadena de longitud n tiene aproximadamente n²/2 subcadenas: 1.25 × 10^9 comprobaciones para n = 5 × 10^4.

Algoritmo

Establece best en 0.
Para cada índice inicial, restablece los 26 contadores y top en 0.
Mueve end desde el inicio hasta el último índice. Suma s[end] a su contador y aumenta top si ese contador es ahora el más alto.
Si end - start + 1 - top ≤ k, guarda la longitud si supera best.
Devuelve 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 ventana deslizante por cada letra objetivo

Intuición

Elige primero la letra final. Si el tramo termina siendo todo A, quieres la subcadena más larga con como máximo k letras que no sean A.

Mueve right a lo largo de la cadena y cuenta las letras que no son el objetivo en la ventana. Cuando el recuento supera k, avanza left hasta que vuelva a ser k. Una ventana que es demasiado costosa sigue siéndolo cuando crece, así que left nunca retrocede y, para cada right, la ventana es la más larga válida que termina ahí.

Ejecuta esto para las 26 letras y quédate con el mejor resultado: 26 pasadas lineales sobre hasta 5 × 10^4 letras. Solo sigue siendo O(n) porque el alfabeto es pequeño.

Algoritmo

Para cada letra objetivo desde A hasta Z, inicia una ventana con left = 0 y others = 0.
Recorre la cadena con right. Si s[right] no es la letra objetivo, suma uno a others.
Mientras others > k, avanza left, restando uno cuando la letra que sale no es la objetivo.
Guarda right - left + 1 si supera a best.
Después de recorrer las 26 letras, devuelve 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 ventana que nunca se encoge

Intuición

Mantén los conteos de las 26 letras para la ventana y top, el conteo más alto. Cuando agregar s[right] hace que la ventana supere el límite, quita una letra de la izquierda: la ventana se desliza y conserva su longitud, ya que solo una ventana más larga puede superar el récord. De lo contrario, crece en uno. Su longitud siempre es la mejor hasta el momento, así que la respuesta es n - left.

Cuando una letra sale, deja top sin cambios, incluso si ahora es mayor que el conteo real. Después de un desplazamiento, la longitud es exactamente top + k, así que para crecer se necesita que alguna letra aparezca top + 1 veces, y top aumenta en ese momento. Un top desactualizado solo puede hacer que la ventana se deslice, y un desplazamiento no puede hacer que se pierda el récord.

En BAAACAB con k = 1, BAAAC necesita 2 cambios y se desliza hasta AAAC. La siguiente A eleva top a 4 y la ventana crece hasta AAACA, con longitud 5.

Algoritmo

Mantén 26 contadores, left = 0 y top = 0.
Mueve right por la cadena: suma s[right] a su contador y aumenta top si ese contador ahora es mayor.
Si right - left + 1 - top > k, elimina s[left] de los contadores y mueve left un paso. Nunca disminuyas top.
Devuelve la longitud final de la ventana, 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

Errores comunes y casos límite

Sumar k a la secuencia más larga. En AAAB, con k = 3, eso da 6, más que la longitud de la cadena. En BAAACAB, con k = 1, da 4, pero cambiar la C une dos secuencias y da 5.
Contar los cambios en comparación con la primera letra de la ventana en lugar de la más frecuente. BAAA necesita un cambio, no tres.
Devolver n - left desde un bucle que reduce la ventana con while y vuelve a calcular el máximo real. Esa ventana se acorta, así que mantén un best separado.
Medir la ventana como right - left. Ambos extremos están dentro de ella, así que suma uno.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Longest Repeating Character Replacement?

La solución de una ventana se ejecuta en tiempo O(n), donde n es la longitud de s: right visita cada letra una vez y left se mueve como máximo una vez por paso. Usa espacio adicional O(1): 26 contadores y algunos enteros.

¿En qué se diferencia esto de la subcadena más larga sin caracteres repetidos?

Ambas desplazan dos bordes sobre la cadena, pero la regla para una ventana válida es diferente. Allí, ningún carácter puede repetirse, así que la ventana se reduce hasta que desaparece la repetición. Aquí, la longitud menos el recuento máximo debe ser como máximo k, así que la ventana puede deslizarse con una longitud fija.

¿Se puede resolver este problema mediante búsqueda binaria?

Sí. Si se puede alcanzar una subcadena de longitud L, también se puede alcanzar cualquier subcadena más corta dentro de ella, así que puedes hacer una búsqueda binaria sobre L. Para cada L, desliza una ventana fija de esa longitud y comprueba si alguna posición necesita como máximo k cambios. Eso es O(n log n), más lento que la solución de una sola ventana.

def characterReplacement(s, k):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

s = "BAAACAB"
k = 1

Salida Esperada

Longest Repeating Character Replacement

Función

Restricciones

Ejemplos

Pistas

Solución

Comprueba cada subcadena

Una ventana deslizante por cada letra objetivo

Una ventana que nunca se encoge

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares