py_palindrome_partitioner

Código comentado línea a línea y paso a paso:

Entregas: py_palindrome_partitioner.py con palindrome_partitioner(s). Rank 04 · nivel 3.

Qué pide (en palabras normales)

Subject (enunciado original)
Given a string `s`, find the minimum number of cuts needed to partition it such that every resulting substring is a palindrome.

A cut divides the string between two characters. With `c` cuts, the string is split into `c + 1` substrings. We want the minimum number of cuts `c` such that all parts are palindromes.

Return this minimum number of cuts (an integer).

Constraints:
- An empty string or a string of length 1 is already a palindrome -> 0 cuts.
- If the entire string is already a palindrome -> 0 cuts.
- In the worst case (all characters are distinct), the result is len(s) - 1 cuts.

Expected file: py_palindrome_partitioner.py
Function signature:
def palindrome_partitioner(s: str) -> int:

Examples:
palindrome_partitioner("aab")
=> 1
palindrome_partitioner("aba")
=> 0
palindrome_partitioner("abc")
=> 2

Programación dinámica sobre prefijos

cuts[i] = mínimo de cortes para los primeros i caracteres. Si s[lo..hi] es palíndromo, el prefijo que acaba en hi se puede resolver con "los cortes del prefijo hasta lo, más un corte justo antes de lo":

cuts[hi + 1] = min(cuts[hi + 1], cuts[lo] + 1)

Falta saber qué substrings son palíndromos. En vez de una tabla n×n, los genero expandiendo desde cada centro (como en "longest palindromic substring"), y en cada expansión actualizo cuts:

cuts = list(range(-1, n))
for center in range(n):
    for lo, hi in ((center, center), (center, center + 1)):
        while lo >= 0 and hi < n and s[lo] == s[hi]:
            cuts[hi + 1] = min(cuts[hi + 1], cuts[lo] + 1)
            lo -= 1
            hi += 1
return max(cuts[n], 0)

O(n²) tiempo, O(n) memoria. La inicialización range(-1, n) da el peor caso (i - 1 cortes) y el -1 en la posición 0 hace que un palíndromo que empieza en 0 cueste -1 + 1 = 0 cortes.

Por qué no fuerza bruta

Probar todas las particiones es exponencial. Con un string de 20 caracteres ya son medio millón; con los ~3 s de timeout, el DP es obligatorio.

Trampas