Longest Repeating Character Replacement

+10

Recibes una cadena s formada por 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 los 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 de una misma letra repetida que puedes formar

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo letras mayúsculas en inglés.
0 ≤ k ≤ s.length

Ejemplos

Entrada: s = "BAAACAB"k = 1
Salida: 5
Explicación: Cambia la C por una A y los índices del 1 al 5 leen AAAAA. Para seis letras se necesitarían dos cambios: los índices del 0 al 5 contienen una B y la C, y los índices del 1 al 6 contienen la C y la última B.

Entrada: s = "AABBBAB"k = 2
Salida: 6
Explicación: En ABBBAB, de los índices 1 a 6, las dos A son las únicas letras que no son B, así que dos cambios dan como resultado BBBBBB. La cadena completa contiene tres A y cuatro B, así que necesita tres cambios.

+17 pruebas ocultas al enviar

Para ir más allá

¿Qué cambia si s puede contener cualquier carácter, no solo las 26 letras mayúsculas?

Pistas

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

0 de 3 abiertas

Solución

El coste de una subcadena es fácil de ver: su longitud menos la cantidad de veces que aparece su letra más frecuente. Lo difícil es no tener que calcular el coste de las n² subcadenas. Una ventana deslizante recorre la cadena una sola vez, y la mejor versión se basa en dos hechos: la ventana nunca tiene que encogerse y el recuento más alto de una letra nunca tiene que disminuir.

Comprueba cada subcadena

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

Intuición

Fija una subcadena. ¿En qué letra debería convertirse? En la que ya aparece con mayor frecuencia, porque todas las demás letras tienen que cambiar. Así que una subcadena de longitud len cuya letra más frecuente aparece top veces necesita len - top cambios, y es alcanzable cuando esa cantidad es como máximo k.

Prueba cada subcadena. Para cada inicio, alarga el final de una letra en una y lleva la cuenta de cada letra, aumentando top a medida que avanzas. Así, cada nueva subcadena requiere una sola actualización en vez de volver a contar desde cero. Se comprueban todas las subcadenas, así que no se puede pasar por alto la más larga que se pueda alcanzar.

Es lento porque una cadena de longitud n tiene aproximadamente n²/2 subcadenas. Para n = 5 × 10^4, son 1.25 × 10^9 comprobaciones, muchas más de las que permite el límite de tiempo.

Algoritmo

Establece best en 0.
Para cada índice de inicio, restablece los 26 conteos y top a 0.
Mueve end desde el inicio hasta el último índice. Añade s[end] a su conteo y aumenta top si ese conteo es ahora el más alto.
Si end - start + 1 - top ≤ k, se puede obtener la subcadena: guarda su 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

Invierte la pregunta y elige primero la letra. Si la cadena final está formada solo por A, la pregunta pasa a ser: ¿cuál es la subcadena más larga con como máximo k letras que no sean A? Ese es un problema clásico de ventana deslizante.

Avanza right por la cadena y cuenta las letras dentro de la ventana que no son la letra objetivo. Cuando ese recuento supera k, avanza left hasta que vuelva a ser k. Ampliar una ventana solo puede añadir letras que haya que cambiar, así que una ventana cuyo costo es demasiado alto seguirá teniendo un costo demasiado alto al ampliarla, y left nunca tendrá que retroceder. Para cada right, la ventana que conservas es la más larga que termina ahí y cumple las condiciones.

Ejecuta esto para las 26 letras y conserva la longitud máxima. Cada ejecución es O(n), así que son 26 pasadas en total, aproximadamente 1.3 × 10^6 pasos para n = 5 × 10^4. Es lineal, pero lee la cadena 26 veces y solo funciona 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 y resta uno a others cuando la letra que sale no sea 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

Gestiona cada letra en una ventana. Lleva un recuento de cada una de las 26 letras dentro de ella y de top, el recuento más alto. La ventana necesita length - top cambios, así que es válida cuando ese valor es como máximo k.

Primer hecho: la ventana nunca tiene que reducirse. Solo te importa superar la mejor longitud encontrada hasta el momento, así que, cuando añadir s[right] hace que la ventana requiera demasiados cambios, elimina una letra por la izquierda. La ventana se desliza un paso y mantiene su longitud. Cuando la ventana no requiere demasiados cambios, crece en uno. Por lo tanto, su longitud siempre es la mejor longitud encontrada hasta el momento, y al final la respuesta es n - left.

Segundo hecho: top nunca tiene que disminuir. Cuando una letra sale por la izquierda, dejas top como está, así que puede ser mayor que el recuento real dentro de la ventana. Eso es seguro. Después de un deslizamiento, la longitud de la ventana es exactamente top + k, así que para hacerla crecer se necesita una letra que aparezca top + 1 veces dentro de la ventana, y en ese momento top aumenta junto con ella. Un top desactualizado puede hacer que la ventana se deslice, pero nunca que crezca por error; y deslizarla no supone perder nada, porque solo una ventana más larga podría superar el récord.

En BAAACAB con k = 1, la ventana crece hasta BAAA y luego BAAAC necesita 2 cambios, así que se desliza hasta AAAC. Al añadir la siguiente A, top aumenta a 4 y la ventana crece hasta AAACA, con longitud 5. La última B hace que se deslice una vez más, así que la respuesta es 5.

Algoritmo

Mantén los conteos de las 26 letras, left = 0 y top = 0.
Mueve right por la cadena: suma s[right] a su conteo y aumenta top si ese conteo ahora es mayor.
Si right - left + 1 - top > k, la ventana necesita demasiados cambios: elimina s[left] de los conteos y mueve left un paso. La ventana se desliza y mantiene su longitud.
Nunca disminuyas top cuando salga una letra.
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

El código de la ventana es corto, así que la mayoría de las respuestas incorrectas se deben a la fórmula del costo o a un atajo que solo parece correcto.

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 el cambio correcto está en el medio y une dos secuencias para formar una de 5.
Contar los cambios respecto de la primera letra de la ventana en lugar de respecto de la letra más frecuente. La ventana BAAA necesita un cambio, no tres.
Devolver n - left en una versión cuya ventana puede reducirse. Ese atajo solo funciona cuando la ventana nunca se acorta, como en el código de una sola ventana de aquí. Si tu bucle reduce la ventana con while y vuelve a calcular el máximo real, guarda un best aparte.
Medir la ventana como right - left. Ambos extremos están dentro de ella, así que suma uno.
Tratar k = 0 como un caso especial. Sin cambios, la regla de la ventana ya devuelve la secuencia más larga de una sola letra.

Preguntas frecuentes4

¿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 O(1) de espacio adicional: 26 contadores y algunos enteros.

¿Por qué no es necesario actualizar la frecuencia máxima cuando se desliza la ventana?

La ventana solo intenta superar su propio récord. Después de un deslizamiento, su longitud es top + k, así que una ventana buena más larga necesita que alguna letra aparezca más de top veces, y eso aumenta top de todos modos. Un top demasiado alto solo mantiene la ventana en esa longitud; nunca hace que crezca cuando no debería.

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

Ambos mueven dos extremos por la cadena, pero la regla para que una ventana sea válida es distinta. En ese caso, una ventana es válida cuando ningún carácter se repite, y debe encogerse hasta que desaparezca la repetición. Aquí, una ventana es válida cuando su longitud menos el conteo de su letra más frecuente es como máximo k, lo que permite que la ventana se deslice con una longitud fija en lugar de encogerse.

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

Sí. Si se puede alcanzar alguna 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, pero es una respuesta razonable.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "BAAACAB"
k = 1

Esperado

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 frecuentes4

Problemas similares