$ cat longest-palindromic-substring.md

Longest Palindromic Substring

Solución Conceptual

Si analizamos el problema, veremos que primero nos dan las siguientes instrucciones:

Nos ofrecen los ejemplos:

Example 1:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

Con las restricciones:

1 <= s.length <= 1000
s consist of only digits and English letters.

Vamos a tomar, por ejemplo, el string ‘babad’, la subcadena palidrómica más larga significa que, si al leer una palabra en un sentido, por ejemplo de izquierda a derecha, o en el otro, es decir, de derecha a izquierda, al final termine siendo la misma palabra. En el caso de babad la subcadena más larga serían tanto ‘bab’ como ‘aba’, ya que ambas se pueden leer igual si las lees de derecha a izquierda como de izquierda a derecha.

La primera aproximación del problema, naturalmente, sería hacer fuerza bruta y revisar carácter por carácter, formando así todas las posibles subcadenas en s:

1. [b]
2. [b,a]
3. [b,a,b]
4. [b,a,b,a]
5. [b,a,b,a,d]
6. [a]
7. [a,b]
8. [a,b,a]
      .
      .
      .

Ahora, ¿Cuál es la complejidad en tiempo para revisar si es un palíndromo? Pues, tenemos que revisar por todo el string, así que, para cualquier subcadena de caracteres dada, va a tomar una complejidad temporal lineal Nuestra pregunta cambia, ¿Cuál es la cantidad de substrings que tenemos que revisar que sean palíndromos, digamos $n$ como los datos de entrada, ahora, la cantidad de substrings que tenemos que revisar depende de revisar cada substring con cada caracter, así que tenemos $n^2$.

$$n\cdot n^2 => O(n^3)$$

Entonces, esto no es muy eficiente, pero funciona.

¿Cómo lo hacemos mejor?

Ahora podríamos revisar los extremos, por ejemplo de babad y tomando la subcadena bab, si revisamos los extremos de la subcadena vamos a ver que son iguales y solo tenemos que recorrernos al centro revisando que sean iguales hasta que estén en la misma posición, pero, también podríamos hacerlo de otro modo.

Podríamos considerar hacer lo opuesto del ejemplo anterior, en lugar de comenzar por los extremos y recorrernos hacia el medio, la otra opción sería comenzar desde el medio y recorrer hacia los extremos.

Para determinar cuál de las dos opciones nos conviene más, podríamos analizar cada una. Primero veamos la segunda opción. Comenzando con el primer caracter de nuestro ejemplo b, tenemos que revisar cuál es el palíndromo más largo donde esta b es el centro del palíndromo, la respuesta es obvia, al ser la primera letra de babad, al estar al inicio, el palíndromo más largo que puede formar siendo ella el centro de la palabra, es ella misma, no hay ningún caracter a su izquierda. Al movernos al caso de a, vemos que ahora si tenemos letras en ambos lados, además, resultan ser iguales, si seguimos así para cada caracter solo tenemos que recorrer la lista una vez y expandir a los lados, entonces la complejidad temporal es ahora

$$n\cdot n = \mathcal{O}(n^2)$$

Si tienes buen ojo, habrás notado que hasta ahora no he considerado que el palíndromo más largo podría ser de longitud par, de hecho, en los ejemplos que nos dan podemos ver que nos dan el caso de longitud par cbbd donde el palíndromo más largo es bb (de longitud par). Simplemente hay que tomarlo como un caso aislado cuando lo implementemos en el código. Para ayudar a la lectura de las variables, voy a utilizar TypeScript para el código.

function longestPalindrome(s: string): string {
  function expand(i: number, j: number): string {
    let left: number = i;
    let right: number = j;

    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }

    return s.slice(left + 1, right);
  }

  let ans: string = "";

  for (let i = 0; i < s.length; i++) {
    let odd: string = expand(i, i);
    if (odd.length > ans.length) {
      ans = odd;
    }
    let even: string = expand(i, i + 1);
    if (even.length > ans.length) {
      ans = even;
    }
  }

  return ans;
}