Palindrome partition dynamic programming in Python

Tabulates palindrome status of all substrings and computes the minimum cuts in O(n^2) time.

File: palindrome_partition_dp.py, 64 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

palindrome_partition_dp.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/palindrome-partition-dp/. The authors are listed in prov/3EX5K9.jsonl.

"""Minimum palindrome partition by dynamic programming over prefixes.

Indices are 0-based and s[j..i] includes both ends. Pieces may be odd or even
palindromes. Symbols are only tested for equality. best[i] is the least number
of palindromes whose concatenation is the prefix s[0..i-1]; the minimum number
of cuts is best[n] - 1 for n >= 1.
"""

from collections.abc import Hashable, Sequence


def min_palindrome_partition(s: Sequence[Hashable]) -> tuple[int, list[tuple[int, int]]]:
    """Return (k, pieces): the least number k of palindromic pieces of s and one such partition.

    Each piece is a pair (j, i) of 0-based inclusive bounds. The empty input
    gives (0, []). Time Theta(n^2), space Theta(n^2).
    """
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    best = [0] * (n + 1)  # @line L1
    start = [0] * (n + 1)
    for i in range(n):  # @line L2
        best[i + 1] = n + 1  # @line L3
        for j in range(i + 1):  # @line L4
            if s[j] == s[i] and (i - j < 2 or pal[j + 1][i - 1]):  # @line L5
                pal[j][i] = True  # @line L6
                if best[j] + 1 < best[i + 1]:  # @line L7
                    best[i + 1] = best[j] + 1
                    start[i + 1] = j
    pieces: list[tuple[int, int]] = []
    i = n  # @line L8
    while i > 0:  # @line L9
        pieces.append((start[i], i - 1))
        i = start[i]
    pieces.reverse()
    return best[n], pieces  # @line L10


def min_cuts(s: Sequence[Hashable]) -> int:
    """Return the least number of cuts that split s into palindromes (0 for the empty string)."""
    k, _ = min_palindrome_partition(s)
    return max(k - 1, 0)


def palindromic_length_linear_space(s: Sequence[Hashable]) -> int:
    """Return the least number of palindromic pieces of s in Theta(n^2) time and O(n) space.

    The 2n - 1 centers are taken from left to right and each one is expanded.
    When the palindrome s[l..r] is found, every palindrome that ends at l - 1
    has a center to the left of the current one, so best[l] is final.
    """
    n = len(s)
    best = [0] + [n + 1] * n
    for c in range(2 * n - 1):
        lo, hi = c // 2, (c + 1) // 2
        while lo >= 0 and hi < n and s[lo] == s[hi]:
            if best[lo] + 1 < best[hi + 1]:
                best[hi + 1] = best[lo] + 1
            lo -= 1
            hi += 1
    return best[n]

test_palindrome_partition_dp.py 78 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/palindrome-partition-dp/. The authors are listed in prov/3EX5K9.jsonl.

import itertools
import random

from palindrome_partition_dp import (
    min_cuts,
    min_palindrome_partition,
    palindromic_length_linear_space,
)


def brute_min(s: str) -> int:
    """Least number of pieces over all 2^(n-1) sets of cuts with only palindromic pieces."""
    n = len(s)
    if n == 0:
        return 0
    best = n
    for mask in range(1 << (n - 1)):
        cuts = [0] + [i + 1 for i in range(n - 1) if mask >> i & 1] + [n]
        if all(s[a:b] == s[a:b][::-1] for a, b in itertools.pairwise(cuts)):
            best = min(best, len(cuts) - 1)
    return best


def check(s: str, k: int, pieces: list[tuple[int, int]]) -> None:
    assert len(pieces) == k
    pos = 0
    for j, i in pieces:
        assert j == pos and i >= j
        assert s[j : i + 1] == s[j : i + 1][::-1]
        pos = i + 1
    assert pos == len(s)


def test_example() -> None:
    assert min_palindrome_partition("banana") == (2, [(0, 0), (1, 5)])
    assert min_palindrome_partition("abaab") == (2, [(0, 0), (1, 4)])
    assert min_cuts("abaab") == 1
    assert min_palindrome_partition("aaba") == (2, [(0, 0), (1, 3)])


def test_edges() -> None:
    assert min_palindrome_partition("") == (0, [])
    assert min_cuts("") == 0
    assert palindromic_length_linear_space("") == 0
    assert min_palindrome_partition("a") == (1, [(0, 0)])
    for n in range(1, 30):
        assert min_palindrome_partition("a" * n) == (1, [(0, n - 1)])
        assert palindromic_length_linear_space("a" * n) == 1
    s = "abc" * 7
    assert min_palindrome_partition(s)[0] == len(s)
    assert palindromic_length_linear_space(s) == len(s)
    assert min_palindrome_partition([1, 2, 1])[0] == 1


def test_random_against_brute_force() -> None:
    rng = random.Random(3509)
    for trial in range(900):
        k = (1, 2, 3)[trial % 3]
        n = rng.randrange(0, 13)
        s = "".join(rng.choice("abc"[:k]) for _ in range(n))
        want = brute_min(s)
        got, pieces = min_palindrome_partition(s)
        assert got == want, s
        check(s, got, pieces)
        assert palindromic_length_linear_space(s) == want
        assert min_cuts(s) == max(want - 1, 0)


def test_longer_inputs_agree() -> None:
    rng = random.Random(77)
    for k in (2, 3):
        s = "".join(rng.choice("abc"[:k]) for _ in range(400))
        got, pieces = min_palindrome_partition(s)
        check(s, got, pieces)
        assert got == palindromic_length_linear_space(s)

What the next level needs

the tests did not run in this build

Read the full page about Palindrome partition dynamic programming