Sesión 42: Grokking Cap. 9 (Parte 3) & CTCI 8.13 — Secuencias y Matrices DP: LCS, Substring, LIS y Stack of Boxes#

Navegación rápida:

• ← Sesión 41: CTCI Ch8 — DP: Coin Change y Permutaciones de Monedas
• Sesión 43: CTCI Ch5 — Bit Manipulation: Fundamentos y Trucos Binarios →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_42.rs

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

En esta sesión concluimos el bloque de Programación Dinámica abordando las estructuras de alineamiento de secuencias y ordenamientos topológicos multidimensionales. Consulta el Glosario Maestro y la Guía de Diagramas.

Longest Common Subsequence (LCS / Subsecuencia Común Más Larga)#

• (a) En palabras simples (intuición): Comparas dos textos para ver qué palabras o letras comparten en el mismo orden de lectura, aunque en medio haya palabras intercaladas que fueron agregadas o borradas. Es la base matemática de cómo git diff detecta qué líneas modificaste en un archivo sin confundirse con el resto.
• (b) Definición técnica paso a paso: Subsecuencia maximal que aparece en el mismo orden secuencial dentro de dos secuencias S₁ y S₂, sin requerir contigüidad física. En una matriz DP de (M + 1) × (N + 1):

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa sobre slices de bytes (&[u8]) mediante s.as_bytes(), indexando directamente en la matriz para evitar el overhead de decodificación UTF-8 en cada iteración.
• (d) Error típico de Junior: Confundir subsecuencia con subcadena: en LCS, ante una discordancia se propaga el valor máximo acumulado; no se pone en cero.

Longest Common Substring (Subcadena Común Contigua y Reinicio a Cero)#

• (a) En palabras simples (intuición): Buscar la frase textual idéntica más larga entre dos libros. Si en un libro dice "el perro negro duerme" y en el otro "el perro blanco duerme", la subcadena común es "el perro " (8 letras seguidas exactas). En cuanto cambia una sola letra ("n" vs "b"), la coincidencia contigua se destruye por completo.
• (b) Definición técnica paso a paso: Segmento continuo de caracteres adyacentes presente en ambas cadenas. La relación de recurrencia es:

El valor óptimo no se encuentra en la esquina final (M, N), sino en el valor máximo absoluto max_{i, j}(dp[i][j]) registrado a lo largo de toda la matriz.

• (c) Cómo funciona en Rust (memoria y tipos): Se registra la longitud máxima y el índice de finalización end_pos_s1, extrayendo la subcadena resultante mediante un slice de bytes contiguo &b1[end - max_len..end].
• (d) Error típico de Junior: Leer únicamente la celda dp[M][N] al terminar; como las últimas letras pueden no coincidir, dp[M][N] valdrá 0 aunque en medio exista una subcadena de 100 caracteres idénticos.

Longest Increasing Subsequence (LIS / Subsecuencia Creciente Más Larga)#

• (a) En palabras simples (intuición): Tienes una fila de personas de distintas estaturas. Quieres elegir al mayor número de personas posible para que, mirándolas de izquierda a derecha, cada una sea estrictamente más alta que la anterior, sin alterar el orden en que estaban formadas.
• (b) Definición técnica paso a paso: Subsecuencia de longitud máxima en la que cada elemento es estrictamente mayor que su predecesor inmediato (aₖ < a_{k+1}).
• DP Cuadrática: O(N²) comparando cada elemento con todos sus predecesores.
• Patience Sorting: O(N log N) manteniendo los extremos mínimos de subsecuencias crecientes de cada longitud.
• (c) Cómo funciona en Rust (memoria y tipos): La versión óptima utiliza un vector auxiliar tails: Vec<i32> y realiza búsqueda binaria mediante el método estándar partition_point.
• (d) Error típico de Junior: Creer que el arreglo tails contiene la subsecuencia creciente resultante; tails solo almacena los candidatos de cola óptimos (minimal tail candidates); su longitud es idéntica a LIS, pero sus elementos no representan necesariamente una subsecuencia válida en su orden original.

Algoritmo de Patience Sorting con Búsqueda Binaria (O(N log N))#

• (a) En palabras simples (intuición): Un solitario de cartas de baraja. Cuando tomas una carta nueva, buscas de izquierda a derecha la primera pila cuya carta superior sea mayor o igual que tu carta, y la colocas encima. Si no hay ninguna pila donde quepa, abres una nueva pila a la derecha. Al final, el número total de pilas de cartas es exactamente la longitud de la subsecuencia creciente más larga.
• (b) Definición técnica paso a paso: Algoritmo propuesto por Mallows y Aldous & Diaconis. Mantiene un arreglo monótonamente creciente tails donde tails[k] es el menor valor final de todas las subsecuencias crecientes encontradas de longitud k + 1. Al procesar x:
• Si x > tails.last(), se añade al final (tails.push(x)), incrementando la longitud LIS en 1.
• Si no, se encuentra el índice k mediante búsqueda binaria tal que tails[k] ≥ x y se actualiza tails[k] = x, permitiendo que subsecuencias futuras se extiendan con mayor facilidad.
• (c) Cómo funciona en Rust (memoria y tipos): Ejecuta tails.partition_point(|&val| val < num) en O(log N) ciclos sin asignaciones dinámicas adicionales una vez reservado el vector.
• (d) Error típico de Junior: Usar bisect_right en lugar de bisect_left (o <= en lugar de < en Rust) para LIS estrictamente creciente, lo que permitiría elementos duplicados iguales.

Apilamiento de Cajas 3D y Reducción a DAG (Stack of Boxes / CTCI 8.13)#

• (a) En palabras simples (intuición): Tienes una pila de cajas de cartón con distintas dimensiones (ancho, alto y profundidad). Para que la torre no se caiga, una caja solo puede colocarse encima de otra si su base cabe holgadamente dentro y además es más baja. Quieres construir la torre más alta posible.
• (b) Definición técnica paso a paso: Problema de optimización geométrica tridimensional. Una caja i = (wᵢ, hᵢ, dᵢ) solo puede apoyarse sobre j = (wⱼ, hⱼ, dⱼ) si:

Al ordenar las cajas de forma descendente por su altura (h), se eliminan dependencias circulares y el problema se reduce a encontrar el camino de peso máximo en un Grafo Acíclico Dirigido (DAG), resuelto mediante una variante ponderada de LIS en O(N²).

• (c) Cómo funciona en Rust (memoria y tipos): Se ordenan las tuplas mediante sorted_boxes.sort_by(|a, b| b.1.cmp(&a.1)) y se computa dp[i] = dp[i].max(dp[j] + h_i) sobre un vector de alturas.
• (d) Error típico de Junior: Permitir igualdad (≤) en alguna de las dimensiones; el enunciado de CTCI exige desigualdad estricta (<) en las tres dimensiones.

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

Diferencia Estructural: Subsecuencia (LCS) vs Subcadena Contigua#

Consideremos dos textos: S1 = "ABAZDC" y S2 = "BACBAD".

Matriz de Subsecuencia Común (LCS):#

Cuando S₁[i-1] ≠ S₂[j-1]:

Esto significa: "Si la letra actual no coincide, no te preocupes: conserva la mejor coincidencia que hayas logrado ignorando este carácter de S₁ o ignorando el de S₂". Las coincidencias pasadas se propagan hacia la derecha y hacia abajo como una ola que nunca decrece.

Matriz de Subcadena Contigua:#

Cuando S₁[i-1] ≠ S₂[j-1]:

Esto significa: "Si la letra actual no coincide exactamente en esta posición relativa, la cadena continua de letras idénticas se cortó. El contador cae a cero de golpe". La única celda que puede sumar es la diagonal superior izquierda inmediatamente anterior: dp[i][j] = 1 + dp[i-1][j-1].

Visualización del Efecto de Reinicio:
LCS (Propaga el récord):        Substring (Resetea al fallar):
[ 0,  1,  1,  1 ]               [ 0,  1,  0,  0 ]
[ 0,  1,  2,  2 ]               [ 0,  0,  2,  0 ]  <-- Si el 3er carácter falla,
[ 0,  1,  2,  3 ]               [ 0,  0,  0,  0 ]  <-- ¡la celda vuelve a 0!

Reconstrucción de la Cadena LCS por Backtracking#

Para obtener la cadena "lue" a partir de "blue" y "clues":

1. Empezamos en la esquina inferior derecha: (i = m, j = n).
2. Si S₁[i-1] == S₂[j-1]: - Este carácter formó parte del alineamiento óptimo. - Lo agregamos al vector de caracteres. - Nos movemos diagonalmente hacia atrás: i = i - 1, j = j - 1.
3. Si los caracteres no coinciden: - Verificamos de cuál celda provino el valor máximo: - Si dp[i-1][j] ≥ dp[i][j-1], el óptimo provino de arriba ⟹ i = i - 1. - Si no, provino de la izquierda ⟹ j = j - 1.
4. Al llegar a i = 0 o j = 0, invertimos el vector de caracteres recolectados.

La Demostración de Patience Sorting (O(N log N)) para LIS#

¿Por qué el algoritmo de paciencia encuentra la longitud correcta en O(N log N)?

Sea la entrada: nums = [10, 9, 2, 5, 3, 7, 101, 18].

1. num = 10: tails = [10]. (Subsecuencia de long 1 termina en 10).
2. num = 9: 9 < 10. Reemplaza 10: tails = [9]. (Es más prometedor que termine en 9 que en 10).
3. num = 2: 2 < 9. Reemplaza 9: tails = [2].
4. num = 5: 5 > 2. Se expande: tails = [2, 5]. (Subsecuencia de long 2 termina en 5).
5. num = 3: Reemplaza 5 con búsqueda binaria: tails = [2, 3]. (Terminar en 3 es mejor que en 5).
6. num = 7: 7 > 3. Se expande: tails = [2, 3, 7]. (Longitud 3).
7. num = 101: 101 > 7. Se expande: tails = [2, 3, 7, 101]. (Longitud 4).
8. num = 18: Reemplaza 101: tails = [2, 3, 7, 18]. (Longitud 4).

Invariante Matemático de tails:

• El arreglo tails se mantiene estrictamente ordenado de forma ascendente en todo momento.
• Esta monotonía permite usar búsqueda binaria (partition_point) para localizar la posición de reemplazo o inserción en tiempo O(log N) para cada uno de los N números.
• Tiempo total: N × O(log N) = O(N log N).

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Transición de Estados#

Consulta el diagrama vectorial:

flowchart TD
    MATCH{"s1[i-1] == s2[j-1]"} -->|Sí: Caracteres idénticos| DIAG["dp[i][j] = 1 + dp[i-1][j-1]<br/>(Avanza en diagonal)"]
    MATCH -->|No: Caracteres distintos| PROBLEM{"¿Tipo de Problema?"}
    PROBLEM -->|LCS Subsecuencia| MAX["dp[i][j] = max(arriba, izquierda)"]
    PROBLEM -->|Substring Contigua| ZERO["dp[i][j] = 0 (Reinicio a cero)"]
    DIAG --> RECORD["Actualizar máximo si supera récord"]
    MAX --> RECORD
    ZERO --> RECORD

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

Analicemos la memoria durante la ejecución de length_of_lis(&[10, 9, 2, 5, 3]):

PASO 1: Creación del vector tails en Heap
Stack: nums = &[10, 9, 2, 5, 3]
Heap: tails = Vec::new() (capacidad inicial 0 o amortizada)

PASO 2: Iteración num = 10
tails.partition_point(|x| x < 10) -> idx = 0 == tails.len() -> push(10)
Heap: tails = [10]

PASO 3: Iteración num = 9
tails.partition_point(|x| x < 9) -> idx = 0 < tails.len() -> tails[0] = 9
Heap: tails = [9]

PASO 4: Iteración num = 2
tails.partition_point(|x| x < 2) -> idx = 0 < tails.len() -> tails[0] = 2
Heap: tails = [2]

PASO 5: Iteración num = 5
tails.partition_point(|x| x < 5) -> idx = 1 == tails.len() -> push(5)
Heap: tails = [2, 5]

PASO 6: Iteración num = 3
tails.partition_point(|x| x < 3) -> idx = 1 < tails.len() -> tails[1] = 3
Heap: tails = [2, 3]

Resultado final retornado: tails.len() = 2.
Costo de memoria en Heap: 2 elementos i32 = 8 bytes.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: Propagar Valores en Subcadena Contigua en Lugar de Resetear a 0#

• El error: Escribir dp[i][j] = dp[i-1][j].max(dp[i][j-1]) al implementar Longest Common Substring.
• Por qué falla: Transforma la subcadena contigua en una subsecuencia discontinua. Al propagar los máximos de casillas anteriores, el algoritmo ignorará que los caracteres contiguos se rompieron y reportará longitudes falsas.
• La solución: Si los caracteres difieren, la celda de subcadena debe asignarse obligatoriamente a 0:

  if b1[i - 1] == b2[j - 1] {
      dp[i][j] = 1 + dp[i - 1][j - 1];
  } else {
      dp[i][j] = 0; // Mandatorio
  }

Trampa 2: Afirmar que el Vector tails Contiene la Subsecuencia Creciente#

• El error: El entrevistador te pide: "Entrégame los números exactos de la subsecuencia creciente más larga", y tú imprimes el contenido del arreglo tails.
• Por qué falla: Para nums = [10, 9, 2, 5, 3, 7, 101, 18], al final tails = [2, 3, 7, 18]. En este caso coincidió, pero para nums = [3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12], los reemplazos por búsqueda binaria mezclan candidatos de distintas ramas históricas. tails no preserva la secuencia cronológica de inserción.
• La solución: Explicar al entrevistador que tails solo preserva los valores mínimos de cola para calcular la longitud en O(N log N). Para reconstruir los elementos exactos se requiere almacenar punteros a padres o usar el enfoque DP clásico O(N²) con backtracking.

Trampa 3: No Ordenar Previamente las Cajas en Stack of Boxes (CTCI 8.13)#

• El error: Ejecutar el bucle anidado O(N²) sobre las cajas en el orden aleatorio en que vienen en el vector de entrada.
• Por qué falla: Si la caja B es más grande que A, pero en el vector B aparece después de A, la evaluación no podrá encadenarlas si solo revisa los índices hacia atrás (j < i). Si permites que revise hacia adelante y hacia atrás sin ordenar, el grafo puede contener ciclos si los datos son ambiguos.
• La solución: Ordenar las cajas de forma descendente por altura antes de empezar la programación dinámica:

  sorted_boxes.sort_by(|a, b| b.1.cmp(&a.1));

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

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

/// LeetCode 1143: LCS en matriz 2D O(M * N).
pub fn longest_common_subsequence(text1: &str, text2: &str) -> usize {
    if text1.is_empty() || text2.is_empty() {
        return 0;
    }

    let s1 = text1.as_bytes();
    let s2 = text2.as_bytes();
    let m = s1.len();
    let n = s2.len();

    let mut dp = vec![vec![0usize; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    dp[m][n]
}

/// Grokking Ch 9: Longest Common Substring contiguo con reinicio a 0.
pub fn longest_common_substring(s1: &str, s2: &str) -> (usize, String) {
    if s1.is_empty() || s2.is_empty() {
        return (0, String::new());
    }

    let b1 = s1.as_bytes();
    let b2 = s2.as_bytes();
    let m = b1.len();
    let n = b2.len();

    let mut dp = vec![vec![0usize; n + 1]; m + 1];
    let mut max_len = 0;
    let mut end_pos_s1 = 0;

    for i in 1..=m {
        for j in 1..=n {
            if b1[i - 1] == b2[j - 1] {
                dp[i][j] = 1 + dp[i - 1][j - 1];
                if dp[i][j] > max_len {
                    max_len = dp[i][j];
                    end_pos_s1 = i;
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }

    let substring = if max_len > 0 {
        String::from_utf8_lossy(&b1[end_pos_s1 - max_len..end_pos_s1]).into_owned()
    } else {
        String::new()
    };

    (max_len, substring)
}

/// LeetCode 300: LIS Óptimo O(N log N) mediante Patience Sorting.
pub fn length_of_lis(nums: &[i32]) -> usize {
    if nums.is_empty() {
        return 0;
    }

    let mut tails = Vec::new();

    for &num in nums {
        let idx = tails.partition_point(|&x| x < num);
        if idx == tails.len() {
            tails.push(num);
        } else {
            tails[idx] = num;
        }
    }

    tails.len()
}

/// CTCI 8.13: Stack of Boxes (Apilamiento con LIS 3D).
pub fn stack_of_boxes(boxes: &[(u32, u32, u32)]) -> u32 {
    if boxes.is_empty() {
        return 0;
    }

    let mut sorted_boxes = boxes.to_vec();
    sorted_boxes.sort_by(|a, b| b.1.cmp(&a.1));

    let n = sorted_boxes.len();
    let mut dp: Vec<u32> = sorted_boxes.iter().map(|b| b.1).collect();

    for i in 0..n {
        let (w_i, h_i, d_i) = sorted_boxes[i];
        for j in 0..i {
            let (w_j, h_j, d_j) = sorted_boxes[j];
            if w_i < w_j && h_i < h_j && d_i < d_j {
                dp[i] = dp[i].max(dp[j] + h_i);
            }
        }
    }

    *dp.iter().max().unwrap_or(&0)
}

Implementación en Python de Referencia (practica/dia_42_dp_lcs_lis_box_stacking.py)#

import bisect
from typing import List, Tuple


def longest_common_subsequence(text1: str, text2: str) -> int:
    """LeetCode 1143: LCS en matriz 2D O(M * N)."""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]


def longest_common_substring(s1: str, s2: str) -> Tuple[int, str]:
    """Grokking Ch 9: Longest Common Substring contiguo con reinicio a 0."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    end_pos_s1 = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos_s1 = i
            else:
                dp[i][j] = 0

    substring = s1[end_pos_s1 - max_len : end_pos_s1] if max_len > 0 else ""
    return max_len, substring


def length_of_lis(nums: List[int]) -> int:
    """LeetCode 300: LIS en O(N log N) con Patience Sorting y Búsqueda Binaria."""
    tails: List[int] = []

    for num in nums:
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num

    return len(tails)


def stack_of_boxes(boxes: List[Tuple[int, int, int]]) -> int:
    """CTCI 8.13: Altura máxima apilando cajas con dimensiones estrictamente menores."""
    if not boxes:
        return 0

    sorted_boxes = sorted(boxes, key=lambda b: b[1], reverse=True)
    n = len(sorted_boxes)
    dp = [sorted_boxes[i][1] for i in range(n)]

    for i in range(n):
        w_i, h_i, d_i = sorted_boxes[i]
        for j in range(i):
            w_j, h_j, d_j = sorted_boxes[j]
            if w_i < w_j and h_i < h_j and d_i < d_j:
                dp[i] = max(dp[i], dp[j] + h_i)

    return max(dp)

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

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Cadenas Completamente Idénticas: - Si S₁ = S₂ = "ALGORITMO", verifica que LCS y Longest Common Substring retornan exactamente la misma longitud 9 y la misma cadena.
2. Paso Límite 2: Arreglo Numérico Estrictamente Decreciente (LIS): - Dado nums = [10, 9, 8, 7, 6, 5], el algoritmo de Patience Sorting debe reemplazar continuamente tails[0], manteniendo tails.len() = 1.
3. Paso Límite 3: Reducción a Russian Doll Envelopes (LeetCode 354): - Tienes sobres con ancho y alto (w, h). Un sobre cabe dentro de otro solo si ambas dimensiones son estrictamente menores. - Demuestra por qué ordenar por ancho ascendente y, en caso de empate, por alto descendente, permite resolver el problema aplicando directamente LIS en O(N log N) sobre las alturas.

Navegación final:

• ← Sesión 41: CTCI Ch8 — DP: Coin Change y Permutaciones de Monedas
• Sesión 43: CTCI Ch5 — Bit Manipulation: Fundamentos y Trucos Binarios →
• Glosario Maestro
• Guía de Diagramas de Arquitectura