Longest Common Prefix

En este artículo analizamos Longest Common Prefix, un problema clásico de manipulación de strings que aparece frecuentemente en entrevistas técnicas de empresas como Google, Amazon y Microsoft. Es excelente para evaluar tu razonamiento lógico y manejo eficiente de cadenas.

Enunciado del problema

Dado un arreglo de strings strs, encuentra el prefijo común más largo entre todos ellos. Si no existe un prefijo común, retorna "".

Ejemplo 1

Entrada: strs = ["flower", "flow", "flight"]
Salida: "fl"

Ejemplo 2

Entrada: strs = ["dog","racecar","car"]
Salida: ""

Ejemplo 3

Entrada: strs = ["interstellar","internet","international"]
Salida: "inter"

Observaciones clave

• Cada carácter en la posición i debe coincidir en todas las palabras.
• El prefijo no puede ser más largo que la palabra más corta.
• La primera discrepancia define el final del prefijo.

Paso a paso: solución óptima

Estrategia

1. Usar la primera palabra como referencia.
2. Comparar carácter por carácter con las demás.
3. Detenerse al encontrar una diferencia.
4. Construir el prefijo acumulando caracteres válidos.

Casos especiales

• Arreglo vacío → ""
• Cadena vacía presente → ""
• Una sola palabra → la palabra completa

Implementación en TypeScript

function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) return '';
  
  let prefix = '';
  let index = 0;
  
  while (true) {
    const current = strs[0][index];
    if (!current) return prefix;
    
    for (const word of strs) {
      if (word[index] !== current) return prefix;
    }
    
    prefix += current;
    index++;
  }
}

Implementación en Python

def longestCommonPrefix(strs: list[str]) -> str:
    if not strs:
        return ""
    
    prefix = ""
    index = 0
    
    while True:
        if index >= len(strs[0]):
            return prefix
        
        current = strs[0][index]
        
        for word in strs:
            if index >= len(word) or word[index] != current:
                return prefix
        
        prefix += current
        index += 1

Complejidad

• Tiempo: O(n * m), donde n es el número de strings y m el largo del prefijo común.
• Espacio: O(1) adicional.

Casos de prueba adicionales

Enfoque alternativo

Ordenar el arreglo y comparar solo la primera y la última palabra.

function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) return '';
  
  strs.sort();
  const first = strs[0];
  const last = strs[strs.length - 1];
  
  let i = 0;
  while (i < first.length && first[i] === last[i]) {
    i++;
  }
  
  return first.substring(0, i);
}

Conclusión

Es un problema ideal para practicar lógica sobre strings, comparación carácter por carácter y manejo de casos borde. La clave es detenerse en la primera discrepancia. La solución es limpia, eficiente y excelente para entrevistas técnicas.