DSA Palindrome Partitioning

The problem

Palindrome Partitioning asks for every way to cut a string into pieces so that each piece is a palindrome. A palindrome is a string that reads the same forwards and backwards. The pieces must cover the string exactly, with no letter left over and no letter used twice.

This article tries the shortest legal piece first at each position. That choice fixes the printed order. The all-single-letter split always prints first, and longer pieces follow.

cases = [
    ("aab", [["a", "a", "b"], ["aa", "b"]]),
    ("aba", [["a", "b", "a"], ["aba"]]),
    ("ab", [["a", "b"]]),
    ("racecar", [["r", "a", "c", "e", "c", "a", "r"], ["r", "a", "cec", "a", "r"], ["r", "aceca", "r"], ["racecar"]]),
]
for text, expected in cases:
    print("string", repr(text), "partitionings:", expected)

The string aab has two partitionings. One uses the piece aa, and the other uses single letters only. Single letters are always palindromes, so every string has at least one partitioning.

Intuition: each gap either holds a cut or not

A string of length n has n minus 1 gaps between its letters. Each gap either holds a cut or stays whole. Two gaps give four cut patterns, and the string aab shows all four.

The first choice is where the first piece ends. For aab, the first piece may be a or aa. The third option, the whole string, fails its palindrome test, because aab reversed is baa.

def is_palindrome(text):
    return text == text[::-1]

text = "aab"
for cuts in [(), (1,), (2,), (1, 2)]:
    pieces = []
    start = 0
    for cut in cuts:
        pieces.append(text[start:cut])
        start = cut
    pieces.append(text[start:])
    ok = all(is_palindrome(piece) for piece in pieces)
    print(pieces, "- every piece a palindrome:", ok)

Four cut patterns exist, and two survive the test. Checking every complete pattern is the brute force. Testing each piece before building on it is the improvement the optimal solution makes.

Brute force: build every split, then test every piece

The brute force builds the pieces for every cut pattern. It tests the pieces only after the full split stands built. A counter records the patterns checked.

def is_palindrome(text):
    return text == text[::-1]

def partitions_brute(text):
    results = []
    checked = [0]
    def search(start, path):
        if start == len(text):
            checked[0] += 1
            if all(is_palindrome(piece) for piece in path):
                results.append(list(path))
            return
        for end in range(start + 1, len(text) + 1):
            path.append(text[start:end])
            search(end, path)
            path.pop()
    search(0, [])
    return results, checked[0]

result, checked = partitions_brute("racecar")
for row in result:
    print(row)
print("partitionings:", len(result))
print("cut patterns checked:", checked)

The brute force checked 64 patterns to keep 4 partitionings. Most patterns die on one bad piece. The brute force still builds the whole split before it finds that out.

The optimal solution: test each piece before building on it

The state is the path of pieces chosen so far plus the start index of the piece now being cut, and the search extends that piece one letter at a time and recurses only past pieces that pass the palindrome test. That one sentence is the whole method.

The guard sits before the recursion, not after it. A failing piece stops its branch at once. No split is ever built on top of a piece that has already failed.

def is_palindrome(text):
    return text == text[::-1]

def partitions(text):
    results = []
    path = []
    def search(start):
        if start == len(text):
            results.append(list(path))
            return
        for end in range(start + 1, len(text) + 1):
            piece = text[start:end]
            if is_palindrome(piece):
                path.append(piece)
                search(end)
                path.pop()
    search(0)
    return results

cases = [
    ("aab", [["a", "a", "b"], ["aa", "b"]]),
    ("aba", [["a", "b", "a"], ["aba"]]),
    ("ab", [["a", "b"]]),
    ("racecar", [["r", "a", "c", "e", "c", "a", "r"], ["r", "a", "cec", "a", "r"], ["r", "aceca", "r"], ["racecar"]]),
]
for text, expected in cases:
    result = partitions(text)
    print("string", repr(text), "->", result, "match:", result == expected)

All four cases match. The printed order follows the shortest-piece-first rule. Longer pieces are tried only after every split through the shorter piece is done.

Walkthrough: splitting aab, piece by piece

The walk prints every piece the search tries at each start index. A true line means the piece joined the path. A false line is the pruning, shown at the moment it happens.

def is_palindrome(text):
    return text == text[::-1]

text = "aab"
path = []
def search(start):
    if start == len(text):
        print("record", list(path))
        return
    for end in range(start + 1, len(text) + 1):
        piece = text[start:end]
        ok = is_palindrome(piece)
        print("at index", start, "- try", repr(piece), "- palindrome:", ok)
        if ok:
            path.append(piece)
            search(end)
            path.pop()
search(0)

The two records are the two partitionings from section 1. The rejected pieces, ab and aab, stopped their branches immediately. Nothing was ever built on top of them.

Complexity

Worst-case time is O(n times 2^n) for a string of length n. A string of one repeated letter makes every cut pattern valid, so all 2^(n-1) partitionings are built, and copying each one costs up to n work.

Extra space is O(n) besides the stored results. The path holds at most one piece per letter, and the pieces together cover the string once.

def is_palindrome(text):
    return text == text[::-1]

def partitions(text):
    results = []
    path = []
    def search(start):
        if start == len(text):
            results.append(list(path))
            return
        for end in range(start + 1, len(text) + 1):
            piece = text[start:end]
            if is_palindrome(piece):
                path.append(piece)
                search(end)
                path.pop()
    search(0)
    return results

for text in ("aaa", "aaaa", "aaaaa"):
    result = partitions(text)
    print("string", repr(text), "- partitionings:", len(result), "- cut patterns:", 2 ** (len(text) - 1))

The counts double with each added letter. That doubling is the exponential cost of this problem, shown as counts rather than as seconds on a clock.

Edge cases and pitfalls

The empty string has one partitioning, the empty list of pieces. It is the same base case the search records when the start index reaches the end of the string. A string with no repeated pattern still splits into single letters, because each single letter passes the test.

def is_palindrome(text):
    return text == text[::-1]

def partitions(text):
    results = []
    path = []
    def search(start):
        if start == len(text):
            results.append(list(path))
            return
        for end in range(start + 1, len(text) + 1):
            piece = text[start:end]
            if is_palindrome(piece):
                path.append(piece)
                search(end)
                path.pop()
    search(0)
    return results

print("empty string:", partitions(""))
print("one letter:", partitions("a"))
print("no long palindrome:", partitions("ab"))
print("two same letters:", partitions("aa"))

The classic mistake tests the whole remaining string instead of the next piece. That test rejects a valid first piece whenever the remainder is not itself a palindrome. The block below puts the two tests side by side.

def is_palindrome(text):
    return text == text[::-1]

print("next piece 'aa' is a palindrome:", is_palindrome("aa"))
print("whole remainder 'aab' is a palindrome:", is_palindrome("aab"))

The piece test passes and the remainder test fails, on the same first cut. Only the piece test belongs in the guard. The remainder gets its own pieces, and its own tests, as the search proceeds.