Sesión 29: Refuerzo y Evaluación de Arrays, Strings & Two Pointers Compuestos#

Navegación rápida:

• ← Sesión 28: Grokking Ch7 — Dijkstra y Consolidación de Semana 4
• Sesión 30: Evaluación — Linked Lists In-Place y Heaps →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_29.rs

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

Iniciamos la Semana 5 consolidando los patrones más recurrentes y exigidos en entrevistas técnicas FAANG sobre estructuras lineales contiguas. Consulta el Glosario Maestro y la Guía de Diagramas.

Ventana Deslizante Dinámica (Dynamic Sliding Window)#

• (a) En palabras simples (intuición): Imagina una oruga de goma elástica sobre una regla de madera. La cabeza avanza casilla por casilla comiendo letras. Si se traga una letra repetida que ya tiene en la panza, la cola se encoge inmediatamente hacia adelante hasta dejar esa letra repetida afuera. El cuerpo de la oruga solo contiene letras distintas en todo momento.
• (b) Definición técnica paso a paso: Técnica algorítmica donde dos índices (start y end) delimitan un subrango continuo [start..end] de una secuencia. El puntero end expande la ventana hacia la derecha de uno en uno, mientras que el puntero start se contrae de forma monótona hacia la derecha cada vez que la ventana viola una invariante de validez (en LC 3: contener caracteres duplicados).
• (c) Cómo funciona en Rust (memoria y tipos): La ventana opera directamente sobre los índices de caracteres o bytes de un &str o &[T]. No requiere clonar cadenas ni asignar nuevos buffers en el Heap.
• (d) Error típico de Junior: Resetear start = 0 o retroceder start cuando aparece un duplicado, destruyendo el progreso y degradando el tiempo a O(N²) o O(N³).

Punteros Convergentes Voraces (Greedy Converging Two Pointers)#

• (a) En palabras simples (intuición): Dos personas paradas en los extremos opuestos de un puente angosto caminando una hacia la otra. En cada paso observan quién tiene la barra de contención más baja. Como el agua siempre se desborda por el lado más bajo, la persona en el extremo más bajo avanza hacia adentro buscando una barra más alta.
• (b) Definición técnica paso a paso: Estrategia de dos punteros inicializados en las fronteras externas de un arreglo (left = 0, right = len - 1). En cada iteración se evalúa la función objetivo y se toma una decisión irrevocable (greedy): mover el puntero cuya cota actual limita e impide obtener una mejora matemática futura.
• (c) Cómo funciona en Rust (memoria y tipos): Trabaja con referencias inmutables &[u32] y dos variables usize en el Stack de la CPU, logrando O(1) memoria auxiliar y cero dependencias de asignación dinámica.
• (d) Error típico de Junior: Mover el puntero más alto o mover ambos sin justificación matemática, perdiendo potencialmente el contenedor con mayor área.

Contracción con Salto O(1) (last_seen)#

• (a) En palabras simples (intuición): En lugar de que la cola de la oruga camine pasito a pasito revisando letra por letra hasta botar la repetida, consulta una libreta donde tiene anotado: "La última 'a' estaba en la posición 3". La cola se teletransporta directamente a la posición 4 en un solo parpadeo.
• (b) Definición técnica paso a paso: Optimización de la contracción en la ventana deslizante mediante una tabla hash o arreglo que mapea caracter -> último_índice_visto. Cuando se lee un caracter c, si last_seen[c] >= start, actualizamos start = last_seen[c] + 1 en tiempo constante O(1), evitando el bucle de contracción paso a paso.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con std::collections::HashMap<char, usize> o un arreglo estático [Option<usize>; 128] en el Stack si el alfabeto es puramente ASCII.
• (d) Error típico de Junior: Omitir la condición last_seen[c] >= start. Si el caracter duplicado ocurrió antes del start actual (fuera de la ventana viva), actualizar ciegamente start causaría que la ventana retroceda hacia la izquierda (el start fantasma), reincorporando duplicados viejos.

Caracteres Unicode vs Bytes en Rust (&str vs Vec<char>)#

• (a) En palabras simples (intuición): En español y en emojis, no todas las letras pesan lo mismo. Una 'a' pesa 1 byte, pero una 'á' pesa 2 bytes y un emoji '🚀' pesa 4 bytes. Si intentas cortar una palabra justo a la mitad de un emoji, la computadora se rompe porque partiste una letra en pedazos.
• (b) Definición técnica paso a paso: En Rust, String y &str son secuencias de bytes codificadas estrictamente en UTF-8 válido. La indexación directa por corchetes s[i] está prohibida porque un índice entero representa un byte, no un punto de código escalar (Unicode Scalar Value). Para iterar caracteres seguros se debe usar s.chars() o s.char_indices().
• (c) Cómo funciona en Rust (memoria y tipos): s.chars() es un iterador que decodifica de 1 a 4 bytes por cada caracter en tiempo lineal sin copiar memoria. Para rebanar (slice) un &str debemos garantizar que los índices coincidan con fronteras válidas de UTF-8 (char_indices).
• (d) Error típico de Junior: Tratar strings en Rust como arreglos de char contiguos de tamaño fijo estilo C o Python 3, causando pánicos en tiempo de ejecución por rebanado en límites ilegales.

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

El Problema de la Ventana Deslizante (LC 3: Subcadena Más Larga sin Repeticiones)#

Analicemos la cadena s = "abba": ¿Por qué tantos programadores cometen errores en esta prueba básica?

1. En el índice 0, vemos 'a'. start = 0. Ventana: "a". max_len = 1. last_seen = {'a': 0}.
2. En el índice 1, vemos 'b'. start = 0. Ventana: "ab". max_len = 2. last_seen = {'a': 0, 'b': 1}.
3. En el índice 2, vemos la segunda 'b'. Como 'b' está en last_seen con índice 1, y 1 ≥ start (1 ≥ 0), existe un duplicado dentro de la ventana viva. - Saltamos start = 1 + 1 = 2. - Ventana nueva: "b" (desde índice 2 hasta 2). curr_len = 2 - 2 + 1 = 1. last_seen = {'a': 0, 'b': 2}.
4. En el índice 3, vemos la segunda 'a'. - Buscamos 'a' en last_seen: nos devuelve el índice 0. - ¡ALERTA CRÍTICA!: ¿Debemos saltar a 0 + 1 = 1? - Si saltáramos a 1, start retrocedería de 2 a 1. La ventana pasaría a ser los índices 1..3 ("bba"), ¡la cual contiene dos veces la letra 'b'! - Como 0 < start (0 es menor que 2), esa 'a' inicial ya quedó fuera de la ventana viva. Se ignora el salto y start se mantiene en 2. - Ventana final: "ba" (longitud 2).

Por esta razón, la condición matemática inviolable es:

Demostración Matemática de Correctitud en Container With Most Water (LC 11)#

El área entre dos líneas en las posiciones L y R (L < R) con alturas h[L] y h[R] viene dada por:

Supongamos sin pérdida de generalidad que la pared izquierda es estrictamente menor: h[L] < h[R]. ¿Qué pasaría si decidiéramos conservar la pared izquierda L y mover la pared derecha a cualquier posición interna R' (donde L < R' < R)?

1. El ancho disminuye estrictamente:
   (R' - L) < (R - L)
2. La nueva altura mínima no puede superar a h[L]:
   min(h[L], h[R']) ≤ h[L]
3. Multiplicando ambas desigualdades:
   Área(L, R') = (R' - L) × min(h[L], h[R']) < (R - L) × h[L] = Área(L, R)

¡Esto demuestra rigurosamente que L jamás podrá formar un área mayor con ninguna otra pared interna! Todos los pares (L, R') quedan descartados en bloque matemáticamente. Por consiguiente, la única posibilidad de encontrar un área mayor en todo el espacio de búsqueda es descartar L incrementando left += 1. La invariante voraz es indestructible.

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

Diagramas de Arquitectura#

• Gráfico SVG vectorial: ![Visualización del Día 29 y Memoria en Rust](../diagrams/sesiones/dia_29.svg)
• Código fuente del diagrama: Fuente Mermaid

Flujo de Decisión en Punteros Convergentes#

flowchart TD
    INIT["Inicializar: left = 0, right = N - 1, max_water = 0"] --> COND{"left < right?"}
    COND -->|No| END["Fin: Retornar max_water"]
    COND -->|Sí| CALC["width = right - left<br/>min_h = min(h[left], h[right])<br/>area = width * min_h"]
    CALC --> UPDATE["max_water = max(max_water, area)"]
    UPDATE --> EVAL{"h[left] < h[right]?"}
    EVAL -->|Sí| INC["left += 1 (Descartar pared izquierda)"]
    EVAL -->|No| DEC["right -= 1 (Descartar pared derecha)"]
    INC --> COND
    DEC --> COND

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Ejecución de length_of_longest_substring("abba"):

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame length_of_longest_sub   |               | HashMap<char, usize>                 |
|   s: &str (ptr, len=4)        |               | Capacidad: 8 buckets                 |
|   start: 0                    |               | [ 'a' -> 0, 'b' -> 1 ]               |
|   max_len: 2                  |               +--------------------------------------+
|   last_seen: HashMap ---------+-------------->| Tabla Hash contigua                  |
+-------------------------------+               +--------------------------------------+

Paso 0: end = 0, char = 'a'
- last_seen['a'] no existe -> last_seen.insert('a', 0)
- curr_len = 0 - 0 + 1 = 1 -> max_len = 1
- Ventana activa: s[0..=0] ("a")

Paso 1: end = 1, char = 'b'
- last_seen['b'] no existe -> last_seen.insert('b', 1)
- curr_len = 1 - 0 + 1 = 2 -> max_len = 2
- Ventana activa: s[0..=1] ("ab")

Paso 2: end = 2, char = 'b'
- last_seen['b'] = 1 >= start (0) -> ¡COLISIÓN EN VENTANA VIVA!
- Contracción instantánea: start = 1 + 1 = 2
- last_seen.insert('b', 2)
- curr_len = 2 - 2 + 1 = 1 -> max_len = 2
- Ventana activa: s[2..=2] ("b")

Paso 3: end = 3, char = 'a'
- last_seen['a'] = 0 < start (2) -> Fuera de ventana. Se ignora.
- last_seen.insert('a', 3)
- curr_len = 3 - 2 + 1 = 2 -> max_len = 2
- Ventana activa: s[2..=3] ("ba")

Resultado final retornado en Stack: 2.

4. Las 3 Trampas Clásicas en Entrevistas#

1. *La Trampa del Retroceso de Ventana (Start Fantasma)*: - Olvidar la validación prev_idx >= start. Si actualizas start = last_seen[c] + 1 de manera incondicional, la ventana retrocederá cuando aparezca un caracter repetido de una fase previa ya descartada, introduciendo errores sutiles e intermitentes.
2. Intentar Probar Todos los Pares en Container With Most Water: - Una solución de fuerza bruta evalúa (N(N-1)) / (2) pares, dando O(N²). Para N = 10⁵, esto requiere 5 × 10⁹ operaciones e incurre en Time Limit Exceeded (TLE). Debes presentar inmediatamente el enfoque de dos punteros convergentes O(N) explicando la invariante de descarte de la pared limitante.
3. Asumir que un Índice Numérico Equivale a un Caracter en Strings: - En Rust, hacer &s[start..end] producirá un pánico (panic!) inmediato si el string contiene tildes, caracteres cirílicos o emojis y el índice cae a mitad de los bytes de un punto de código UTF-8. Para rebanadas seguras, convierte o mapea con char_indices().

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

Implementación Canónica en Rust (practica-rust/dia_29.rs)#

//! Día 29: Refuerzo y Evaluación de Arrays, Strings & Two Pointers Compuestos en Rust.
use std::collections::HashMap;

/// LeetCode 3: Ventana Deslizante con HashMap en O(N) tiempo y O(min(N, Sigma)) espacio.
pub fn length_of_longest_substring(s: &str) -> usize {
    if s.is_empty() {
        return 0;
    }

    let mut last_seen: HashMap<char, usize> = HashMap::new();
    let mut start = 0;
    let mut max_len = 0;

    for (end, c) in s.chars().enumerate() {
        if let Some(&prev_idx) = last_seen.get(&c) {
            if prev_idx >= start {
                start = prev_idx + 1;
            }
        }

        last_seen.insert(c, end);
        let curr_len = end - start + 1;
        if curr_len > max_len {
            max_len = curr_len;
        }
    }

    max_len
}

/// Variante constructiva: Retorna la subrebanada sin clonación de memoria en el Heap.
pub fn longest_substring_without_repeating(s: &str) -> &str {
    if s.is_empty() {
        return "";
    }

    let mut last_seen: HashMap<char, usize> = HashMap::new();
    let mut char_byte_offsets: Vec<usize> = Vec::with_capacity(s.len());
    let mut chars: Vec<char> = Vec::with_capacity(s.len());

    for (byte_offset, c) in s.char_indices() {
        char_byte_offsets.push(byte_offset);
        chars.push(c);
    }
    let total_bytes = s.len();

    let mut start = 0;
    let mut best_start = 0;
    let mut max_len = 0;

    for end in 0..chars.len() {
        let c = chars[end];
        if let Some(&prev_idx) = last_seen.get(&c) {
            if prev_idx >= start {
                start = prev_idx + 1;
            }
        }

        last_seen.insert(c, end);
        let curr_len = end - start + 1;
        if curr_len > max_len {
            max_len = curr_len;
            best_start = start;
        }
    }

    if max_len == 0 {
        return "";
    }

    let byte_start = char_byte_offsets[best_start];
    let best_end = best_start + max_len;
    let byte_end = if best_end < chars.len() {
        char_byte_offsets[best_end]
    } else {
        total_bytes
    };

    &s[byte_start..byte_end]
}

/// LeetCode 11: Punteros convergentes voraces en O(N) tiempo y O(1) espacio auxiliar.
pub fn max_area_container(height: &[u32]) -> u64 {
    if height.len() < 2 {
        return 0;
    }

    let mut left = 0;
    let mut right = height.len() - 1;
    let mut max_water: u64 = 0;

    while left < right {
        let width = (right - left) as u64;
        let h_left = height[left] as u64;
        let h_right = height[right] as u64;
        let min_h = h_left.min(h_right);
        let area = width * min_h;

        if area > max_water {
            max_water = area;
        }

        if h_left < h_right {
            left += 1;
        } else {
            right -= 1;
        }
    }

    max_water
}

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

    #[test]
    fn test_length_of_longest_substring() {
        assert_eq!(length_of_longest_substring("abcabcbb"), 3);
        assert_eq!(length_of_longest_substring("bbbbb"), 1);
        assert_eq!(length_of_longest_substring("pwwkew"), 3);
        assert_eq!(length_of_longest_substring("abba"), 2);
    }

    #[test]
    fn test_max_area_container() {
        let heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];
        assert_eq!(max_area_container(&heights), 49);
    }
}

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

from typing import Dict, List, Tuple

def length_of_longest_substring(s: str) -> int:
    """LC 3: Ventana Deslizante con Hash Map en O(N) tiempo y O(min(N, Sigma)) espacio."""
    if not s:
        return 0

    last_seen: Dict[str, int] = {}
    start = 0
    max_len = 0

    for end, char in enumerate(s):
        if char in last_seen and last_seen[char] >= start:
            start = last_seen[char] + 1
        
        last_seen[char] = end
        curr_len = end - start + 1
        if curr_len > max_len:
            max_len = curr_len

    return max_len

def max_area_container(height: List[int]) -> int:
    """LC 11: Punteros convergentes voraces en O(N) tiempo y O(1) espacio."""
    if len(height) < 2:
        return 0

    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        h_left, h_right = height[left], height[right]
        min_h = h_left if h_left < h_right else h_right
        area = width * min_h

        if area > max_water:
            max_water = area

        if h_left < h_right:
            left += 1
        else:
            right -= 1

    return max_water

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

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

1. LeetCode 3 — Longest Substring Without Repeating Characters (Medium): - Resuelve el problema aplicando la ventana deslizante con Hash Map de última posición.
2. LeetCode 11 — Container With Most Water (Medium): - Aplica los punteros convergentes y formula la justificación matemática ante el entrevistador.
3. LeetCode 424 — Longest Repeating Character Replacement (Medium): - Extensión avanzada: ventana deslizante rastreando la frecuencia máxima del caracter dominante con cota de reemplazo k.
4. LeetCode 76 — Minimum Window Substring (Hard): - El reto supremo de ventana deslizante con dos Hash Maps y contador de caracteres satisfechos.

8. Tarea en Papel para Hoy#

Toma una hoja en blanco y tu lápiz:

1. Simula paso a paso con una tabla de variables completa la ejecución de length_of_longest_substring("tmmzuxt").
2. Identifica en qué paso se detecta la duplicación de la letra 'm', a qué índice se actualiza start, y qué ocurre al procesar la 't' final.
3. Dibuja las dos paredes de mayor altura en el vector [2, 3, 4, 5, 18, 17, 6] y traza manualmente la convergencia de left y right hasta hallar el área óptima.

Navegación:

• ← Volver a Sesión 28: Grokking Ch7 — Algoritmo de Dijkstra y Consolidación de Semana 4
• Avanzar a Sesión 30: Evaluación — Linked Lists In-Place y Heaps →