String Compression

Q: ¿Cuál es la complejidad temporal de la compresión de cadenas?

El recorrido con dos punteros tarda O(n) , porque el índice de exploración solo avanza. Además del resultado, mantiene dos índices, por lo que el espacio adicional es O(1) .

FácilDos punteros Arrays y cadenas

+10

Recibes una cadena s de letras inglesas. Comprímela: reemplaza cada secuencia de dos o más letras iguales consecutivas por esa letra seguida de la longitud de la secuencia, y deja tal cual las letras que aparecen solas. Así, aabccc se convierte en a2bc3. Devuelve la cadena comprimida.

Las mayúsculas y las minúsculas son letras diferentes: aA son dos secuencias de longitud 1.

Función

compress(s: string) → string

sstring: la cadena que se va a comprimir, solo letras inglesas
Devuelvestring: la cadena comprimida, cada secuencia escrita como su letra seguida de su longitud cuando la longitud es mayor que 1

Restricciones

1 ≤ s.length ≤ 2 × 10⁴
s contiene solo letras inglesas, de la a a la z y de la A a la Z.
La longitud de una secuencia se escribe en decimal y puede tener varios dígitos.

Ejemplos

Entrada: s = "aabccc"
Salida: "a2bc3"
Explicación: Las rachas son aa, b y ccc. Se convierten en a2, b (una letra sola no lleva contador) y c3.

Entrada: s = "abbbbbbbbbbbb"
Salida: "ab12"
Explicación: Una a, después doce b. La longitud 12 se escribe con los dos caracteres 1 y 2, así que el resultado es ab12.

Entrada: s = "zzZZZ"
Salida: "z2Z3"
Explicación: La letra z minúscula y la letra Z mayúscula son diferentes, así que esto es una secuencia de dos seguida de una secuencia de tres: z2Z3.

Para ir más allá

Escribe la operación inversa: dado un texto comprimido como ab12, reconstruye el original. ¿Cómo lees un número de repeticiones que tiene varios dígitos?

Pistas

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

0 de 3 abiertas

Solución

Encuentra dónde empieza y termina cada secuencia de letras iguales y luego escribe su longitud como texto. Las secuencias de una sola letra no llevan contador, y un contador puede tener varios dígitos. Dos índices, uno al inicio de una secuencia y otro que recorre hasta su final, lo hacen en una sola pasada.

Recopila las ejecuciones y después escríbelas

Intuición

Primero, registra las secuencias como pares de una letra y una longitud: para aabccc, (a, 2), (b, 1), (c, 3). Cada letra extiende la última secuencia o inicia una nueva. Después, escribe la letra de cada secuencia, seguida de su longitud cuando sea mayor que 1.

Ambos recorridos son O(n). La lista puede contener n secuencias cuando no coinciden dos elementos vecinos, así que requiere O(n) espacio adicional.

Algoritmo

Crea una lista vacía de secuencias.
Para cada letra de s: si la última secuencia tiene la misma letra, suma 1 a su longitud; de lo contrario, añade una nueva secuencia de longitud 1.
Para cada secuencia, escribe su letra y después su longitud como texto decimal si la longitud es mayor que 1.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Dos punteros sobre cada secuencia

Intuición

Mantén i en la primera letra de la secuencia actual y avanza j mientras s[j] sea igual a s[i]. Cuando j se detenga, ante una letra distinta o al final, la longitud de la secuencia es j-i. Escríbela y asigna i = j. En abbbbbbbbbbbb, j se detiene primero en 1, dando a, y luego en 13, dando b12.

La última secuencia no requiere un caso especial, porque el bucle interno se detiene al llegar al final de la cadena. j solo avanza, así que el tiempo es O(n), y además del resultado conservas dos índices. Las versiones de R y Swift dividen s primero en un arreglo de caracteres, así que usan O(n) de espacio adicional.

Algoritmo

Establece i = 0.
Mientras i esté dentro de la cadena, establece j = i y avanza j mientras esté dentro de la cadena y s[j] sea igual a s[i].
Escribe s[i]; si j-i es mayor que 1, escríbelo como texto decimal.
Establece i = j y repite.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Errores comunes y casos límite

Escribir una secuencia solo cuando encuentras una letra diferente. No hay nada después del ccc final de aabccc, así que devuelves a2b.
Escribir el recuento como un solo carácter, como '0' + count. Falla al llegar a 10: se necesitan los dos caracteres 12 para doce b.
Escribir 1 después de una letra aislada. b se queda como b, no como b1.
Ignorar las mayúsculas y minúsculas. zzZZZ es z2Z3, no z5.
Hacer crecer una cadena inmutable con +, como en Java o C#. Cada + copia el resultado obtenido hasta ese momento, lo que hace que el bucle tenga una complejidad de O(n²); usa un constructor de cadenas.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de la compresión de cadenas?

El recorrido con dos punteros tarda O(n), porque el índice de exploración solo avanza. Además del resultado, mantiene dos índices, por lo que el espacio adicional es O(1).

¿Puede la cadena comprimida ser más larga que la original?

No en esta versión. Una letra aislada sigue siendo un carácter, y una secuencia de k ≥ 2 letras se convierte en una letra más los dígitos de k, nunca más de k caracteres. Un esquema que escribe un recuento después de cada letra, como a1b1, puede duplicar la longitud.

¿Cómo comprimes una cadena in situ?

Usa un arreglo de caracteres con un índice de lectura y un índice de escritura. Recorre cada secuencia con el índice de lectura y después escribe su letra y los dígitos de su longitud en el índice de escritura. La salida nunca es más larga que la entrada leída hasta el momento, así que el índice de escritura nunca supera al índice de lectura. Devuelve la nueva longitud al final.

def compress(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "aabccc"

Salida Esperada

"a2bc3"