Sesión 06: Cracking the Coding Interview (Capítulo 1, Parte 4) — Strings Avanzados, Compresión y Rotaciones#

Navegación rápida:

• ← Sesión 05: Técnica de Dos Punteros
• Sesión 07: Matrices 2D y Consolidación de Semana 1 →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 50-65 minutos.
• Código fuente compilado y probado: practica-rust/dia_06.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

La manipulación de cadenas a nivel de bits y bytes requiere comprender la mutabilidad, la sobreescritura in-place y la detección de patrones cíclicos. Consulta el Glosario Maestro.

Distancia de Edición Unitaria (One Away / Levenshtein Distance ≤ 1)#

• (a) En palabras simples (intuición): Dos palabras son "casi idénticas" si puedes transformar una en la otra cambiando una sola letra, borrando una sola letra o agregando una sola letra. Si necesitas dos o más cambios, ya no están a distancia unitaria.
• (b) Definición técnica paso a paso: Métrica que evalúa si dos secuencias difieren en a lo sumo una operación elemental de edición: inserción (Δ L = +1), eliminación (Δ L = -1) o sustitución (Δ L = 0). Permite una verificación lineal O(N) sin necesidad de la matriz completa de Programación Dinámica O(N²).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa sobre slices de bytes &[u8]. La diferencia de longitudes (b1.len() as isize - b2.len() as isize).abs() > 1 descarta discrepancias en O(1) antes de recorrer la memoria.
• (d) Error típico de Junior: Intentar resolver este problema generando todas las combinaciones posibles de cadenas o recurriendo a tablas de Programación Dinámica innecesariamente pesadas para un umbral ≤ 1.

Compresión Run-Length (Run-Length Encoding - RLE)#

• (a) En palabras simples (intuición): En lugar de decir "tengo una manzana, una manzana, una manzana, una manzana y una pera", dices "tengo 4 manzanas y 1 pera". Abreviar las repeticiones consecutivas ahorra espacio.
• (b) Definición técnica paso a paso: Forma básica de compresión de datos sin pérdida donde secuencias continuas del mismo símbolo (run) se almacenan como un único símbolo seguido de su conteo entero de repeticiones.
• (c) Cómo funciona en Rust (memoria y tipos): Si la cadena comprimida resultante tiene una longitud mayor o igual a la original, se descarta y se devuelve la cadena original. En Rust se preasigna String::with_capacity(s.len()) para evitar sobrecostos en el Heap.
• (d) Error típico de Junior: Devolver la cadena comprimida a ciegas sin verificar si "abcdef" se convirtió en "a1b1c1d1e1f1" (el doble de grande que la original).

Puntero de Anclaje (Anchor Pointer)#

• (a) En palabras simples (intuición): Una chincheta o alfiler que dejas clavado en el primer elemento de un grupo repetido para recordar dónde empezó mientras caminas buscando dónde termina.
• (b) Definición técnica paso a paso: En algoritmos de dos punteros sobre secuencias contiguas, el anchor marca el índice de inicio del bloque homogéneo actual, mientras que el puntero de lectura explora hacia adelante hasta que el valor cambia. La longitud del bloque se calcula directamente como readᵢdx - anchor + 1.
• (c) Cómo funciona en Rust (memoria y tipos): Permite mutar slices in-place (&mut [char]) sin estructuras auxiliares ni llamadas recursivas.
• (d) Error típico de Junior: Olvidar convertir los conteos numéricos de dos o más dígitos (como 12) en caracteres individuales '1' y '2' al comprimir in-place.

Rotación Cíclica de Cadenas (String Rotation)#

• (a) En palabras simples (intuición): Un collar de cuentas circulares. No importa dónde cortes el collar y lo extiendas sobre la mesa, la secuencia cíclica de cuentas siempre es la misma.
• (b) Definición técnica paso a paso: Una cadena s₂ es una rotación de s₁ si existen dos subcadenas x e y tales que s₁ = xy y s₂ = yx.
• (c) Cómo funciona en Rust (memoria y tipos): La propiedad matemática fundamental establece que yx es siempre una subcadena de xyxy. Por tanto, s₂ es rotación de s₁ si y solo si (s₁ + s₁) contiene a s₂ y ambas tienen la misma longitud.
• (d) Error típico de Junior: Probar todas las N rotaciones posibles manualmente mediante operaciones de slice y concatenación en bucle (O(N²)).

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Rotación Cíclica: Demostración Formal de (s₁ + s₁)#

Supongamos que s₁ = "waterbottle". Podemos partir s₁ en dos fragmentos contiguos arbitrarios:

• x = "wat"
• y = "erbottle"

Por definición:

Una rotación válida mueve el prefijo x al final:

¿Qué sucede si duplicamos y concatenamos s₁ consigo misma?

¡Observa con atención el centro de la expresión resultante! El término yx (que es exactamente s₂) emerge de forma natural y continua dentro de la cadena duplicada. Por consiguiente:

En lugar de rotar la cadena N veces en un bucle costoso, basta con una sola llamada a la función de búsqueda de subcadenas (doubled.contains(s2)). La complejidad temporal pasa de O(N²) a O(N) con espacio O(N).

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Flujo de Compresión de Cadenas#

Consulta el diagrama de arquitectura y flujo del sistema:

• Gráfico SVG: ![Visualización del Día 06 y Memoria en Rust](../diagrams/sesiones/dia_06.svg)
• Enlace al código fuente Mermaid: Fuente Mermaid

flowchart LR
    S["Entrada: 'aabcccccaaa'"] --> COUNT["Contar caracteres consecutivos"]
    COUNT --> BUF["String::push(char) + push_str(count)"]
    BUF --> CHECK{"compressed.len() < original.len()"}
    CHECK -->|Sí| RETC["Retornar comprimido ('a2b1c5a3')"]
    CHECK -->|No| RETO["Retornar original"]

Visualización Cuadro por Cuadro de Memoria: Compresión In-Place (LeetCode 443)#

Entrada: let mut chars = ['a', 'a', 'b', 'b', 'c', 'c', 'c'];

ESTADO INICIAL:
write_idx = 0, anchor = 0
Índices:       0    1    2    3    4    5    6
Valores:     ['a', 'a', 'b', 'b', 'c', 'c', 'c']
               ^
          anchor, read

PASO 1 (read_idx = 0..1):
- chars[0] == 'a', chars[1] == 'a'.
- En read_idx = 1, el siguiente (chars[2]) es 'b' (cambio de carácter).
- count = 1 - 0 + 1 = 2.
- Escribir carácter: chars[write_idx] = 'a' -> write_idx = 1.
- Escribir conteo: chars[write_idx] = '2' -> write_idx = 2.
- Nuevo anchor = 2.
Buffer:      ['a', '2', 'b', 'b', 'c', 'c', 'c']
                         ^
                    anchor, read

PASO 2 (read_idx = 2..3):
- chars[2] == 'b', chars[3] == 'b'.
- En read_idx = 3, el siguiente es 'c'.
- count = 3 - 2 + 1 = 2.
- Escribir 'b' en chars[2] -> write_idx = 3.
- Escribir '2' en chars[3] -> write_idx = 4.
- Nuevo anchor = 4.
Buffer:      ['a', '2', 'b', '2', 'c', 'c', 'c']
                                   ^
                              anchor, read

PASO 3 (read_idx = 4..6):
- chars[4..6] son 'c'. Llega al final del arreglo (read_idx + 1 == 7).
- count = 6 - 4 + 1 = 3.
- Escribir 'c' en chars[4] -> write_idx = 5.
- Escribir '3' en chars[5] -> write_idx = 6.
Buffer:      ['a', '2', 'b', '2', 'c', '3', 'c']
Resultado: Retorna nueva longitud write_idx = 6 (&chars[..6] == ['a', '2', 'b', '2', 'c', '3']).

4. Implementación Canónica en Rust + Comparativa con Python#

Implementación en Rust (practica-rust/dia_06.rs)#

//! Implementación canónica de algoritmos avanzados de strings en Rust.
//! Compilable y verificable con `rustc --test`.

/// CTCI 1.5: Determina si dos cadenas están a distancia de edición <= 1 en O(N).
pub fn one_away(s1: &str, s2: &str) -> bool {
    let b1 = s1.as_bytes();
    let b2 = s2.as_bytes();

    let diff = (b1.len() as isize - b2.len() as isize).abs();
    if diff > 1 {
        return false;
    }

    if b1.len() == b2.len() {
        let mut found_difference = false;
        for i in 0..b1.len() {
            if b1[i] != b2[i] {
                if found_difference {
                    return false;
                }
                found_difference = true;
            }
        }
        return true;
    }

    let (shorter, longer) = if b1.len() < b2.len() {
        (b1, b2)
    } else {
        (b2, b1)
    };

    let mut idx_short = 0;
    let mut idx_long = 0;

    while idx_short < shorter.len() && idx_long < longer.len() {
        if shorter[idx_short] != longer[idx_long] {
            if idx_short != idx_long {
                return false;
            }
            idx_long += 1;
        } else {
            idx_short += 1;
            idx_long += 1;
        }
    }

    true
}

/// CTCI 1.6: Compresión básica Run-Length con descarte si no reduce tamaño.
pub fn compress_string_basic(s: &str) -> String {
    if s.is_empty() {
        return String::new();
    }

    let bytes = s.as_bytes();
    let mut compressed = String::with_capacity(s.len());
    let mut count = 0;

    for i in 0..bytes.len() {
        count += 1;

        if i + 1 == bytes.len() || bytes[i] != bytes[i + 1] {
            compressed.push(bytes[i] as char);
            compressed.push_str(&count.to_string());
            count = 0;
        }
    }

    if compressed.len() < s.len() {
        compressed
    } else {
        s.to_string()
    }
}

/// LeetCode 443: Compresión in-place con soporte para dígitos múltiples.
pub fn compress_in_place(chars: &mut [char]) -> usize {
    let mut write_idx = 0;
    let mut anchor = 0;

    for read_idx in 0..chars.len() {
        if read_idx + 1 == chars.len() || chars[read_idx] != chars[read_idx + 1] {
            chars[write_idx] = chars[anchor];
            write_idx += 1;

            let count = read_idx - anchor + 1;
            if count > 1 {
                for digit in count.to_string().chars() {
                    chars[write_idx] = digit;
                    write_idx += 1;
                }
            }
            anchor = read_idx + 1;
        }
    }

    write_idx
}

/// CTCI 1.9: Rotación de cadenas mediante duplicación en O(N).
pub fn is_string_rotation(s1: &str, s2: &str) -> bool {
    if s1.len() != s2.len() || s1.is_empty() {
        return false;
    }

    let mut doubled = String::with_capacity(s1.len() * 2);
    doubled.push_str(s1);
    doubled.push_str(s1);

    doubled.contains(s2)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_one_away() {
        assert!(one_away("pale", "ple"));
        assert!(one_away("pales", "pale"));
        assert!(one_away("pale", "bale"));
        assert!(!one_away("pale", "bake"));
    }

    #[test]
    fn test_compress_string_basic() {
        assert_eq!(compress_string_basic("aabcccccaaa"), "a2b1c5a3");
        assert_eq!(compress_string_basic("abcdef"), "abcdef");
    }

    #[test]
    fn test_compress_in_place() {
        let mut chars = ['a', 'a', 'b', 'b', 'c', 'c', 'c'];
        let len = compress_in_place(&mut chars);
        assert_eq!(len, 6);
    }

    #[test]
    fn test_is_string_rotation() {
        assert!(is_string_rotation("waterbottle", "erbottlewat"));
        assert!(!is_string_rotation("aa", "a"));
    }
}

Implementación Canónica en Python (practica/dia_06_string_compression.py)#

def one_away(s1: str, s2: str) -> bool:
    if abs(len(s1) - len(s2)) > 1:
        return False
    if len(s1) == len(s2):
        diffs = sum(1 for a, b in zip(s1, s2) if a != b)
        return diffs <= 1

    shorter, longer = (s1, s2) if len(s1) < len(s2) else (s2, s1)
    i, j = 0, 0
    while i < len(shorter) and j < len(longer):
        if shorter[i] != longer[j]:
            if i != j:
                return False
            j += 1
        else:
            i += 1
            j += 1
    return True

def is_string_rotation(s1: str, s2: str) -> bool:
    if len(s1) != len(s2) or not s1:
        return False
    return s2 in (s1 + s1)

5. Las 3 Trampas Clásicas en Entrevistas#

1. Retornar Cadenas Comprimidas Más Largas: - Para cadenas con pocos duplicados (como "abc"), la compresión produce "a1b1c1", cuya longitud es 6 (el doble). La especificación exige explícitamente devolver la original si la comprimida no es estrictamente menor.
2. Conteos con Múltiples Dígitos en Compresión In-Place: - Si un carácter se repite 12 veces, no puedes escribir el número 12 en una sola celda char. Debes descomponer el número en los caracteres '1' y '2', ocupando dos posiciones consecutivas en el búfer.
3. Casos Borde en Rotación: - Cadenas vacías ("" y ""): "".contains("") es verdadero en la mayoría de lenguajes, pero dos cadenas vacías no constituyen una rotación válida. Siempre valida !s1.is_empty().

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 443 — String Compression (Medium): - Implementa la compresión in-place con dos punteros (write_idx y anchor).
2. LeetCode 161 — One Edit Distance (Medium): - Resuelve con la lógica canónica de one_away.
3. LeetCode 796 — Rotate String (Easy): - Aplica el patrón de duplicación (A + A).contains(B).

Navegación:

• ← Volver a Sesión 05: Técnica de Dos Punteros
• Avanzar a Sesión 07: Matrices 2D y Consolidación →