Palindrome Partitioning

Q: What is the time complexity of Palindrome Partitioning?

On a string of equal letters all 2^(n-1) splits are answers, each up to 2n-1 characters long: O(n × 2^n) . No method beats that, because writing the answer costs as much. The palindrome table adds O(n²) time and space, and the recursion O(n) .

Q: How many palindrome partitions can a string have?

At most 2^(n-1) , one for each way to choose which of the n-1 gaps to cut. A string of equal letters reaches that bound: 1,024 splits for 11 letters. A string with no repeated letters has exactly one split, every letter on its own.

Q: Is Palindrome Partitioning dynamic programming or backtracking?

It uses both. Listing up to 2^(n-1) splits takes a search that builds each split piece by piece: backtracking. Dynamic programming supplies the yes or no table of palindromic substrings that the search reads, filled once in O(n²) .

MediumBacktracking Dynamic programming

+10

A palindrome reads the same from left to right and from right to left. Cut the string s into one or more pieces so that every piece is a palindrome, and return every way to do it.

Write each split as its pieces in order, joined by |: cutting aab into a, a and b gives a|a|b. Return the splits sorted in ascending order, comparing character codes, so | comes after every lowercase letter.

Function

partition(s: string) → string-array

sstring: the string of lowercase letters to cut
Returnsstring-array: every split of s into palindromes, written with | between the pieces, in ascending order

Constraints

1 ≤ s.length ≤ 11
s contains only lowercase English letters.
A string of 11 equal letters has 1,024 splits, the largest answer.

Examples

Input: s = "aab"
Output: ["aa|b", "a|a|b"]
Explanation: Only aa|b and a|a|b have all palindromic pieces; a|ab fails on ab. aa|b sorts first: at the second character it has a where the other has |, which sorts after every letter.

Input: s = "abba"
Output: ["abba", "a|bb|a", "a|b|b|a"]
Explanation: abba is itself a palindrome, so the uncut string is a split and sorts first: its second character is a letter. a|bb|a comes before a|b|b|a: at the fourth character it has b where the other has |.

Follow-up

Can you find the smallest number of cuts that splits s into palindromes, for strings of length up to 2,000?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Each of the n-1 gaps between letters is cut or not, so there are 2^(n-1) splits, and all of them can be answers. You cannot beat the output size, but you can skip splits that fail: build each split left to right, cut off only palindromic pieces, and read palindromes from a table filled once.

Try every set of cuts

Intuition

Number the splits with the integers 0 to 2^(n-1)-1, each bit saying whether one gap is cut. Keep a number's split if every piece is a palindrome.

If the first gap gets the highest bit, counting up lists the splits in ascending order. For two numbers, the highest bit where they differ is the earliest gap that one cuts and the other does not. Before it the strings are equal; there the smaller number has a letter and the larger has |, which sorts after every letter. For aab, 1 gives aa|b and 3 gives a|a|b.

At 11 letters that is 1,024 masks of 11 letters each. The waste is in rejected splits: abcdefghijk builds all 1,024 to find one answer.

Algorithm

Loop mask from 0 to 2^(n-1)-1.
Walk the letters; end a piece after letter i when i is the last index or bit n-2-i of mask is set.
Check each piece with two pointers moving inward.
If every piece is a palindrome, join the pieces with | and add the string to the answer.
Return the answer; it is already sorted because the first gap is the highest bit.

def partition(s):
    n = len(s)
    result = []
    # Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
    # masks up from 0 lists the splits in sorted order.
    for mask in range(1 << (n - 1)):
        pieces = []
        start = 0
        for i in range(n):
            if i == n - 1 or (mask >> (n - 2 - i)) & 1:
                pieces.append(s[start:i + 1])
                start = i + 1
        if all(piece == piece[::-1] for piece in pieces):
            result.append("|".join(pieces))
    return result

Backtracking with a palindrome table

Intuition

The first piece is a palindromic prefix s[0..end], and splitting the rest is the same problem from end+1. So backtrack(start) tries every end where s[start..end] is a palindrome, adds the piece, recurses, and removes it. Every branch ends in an answer, since a single letter is a palindrome, so the work follows the output size: for abcdefghijk the search walks one path.

Whether s[start..end] is a palindrome comes up in many branches, so read it from a table: s[i..j] is one when s[i] == s[j] and the inside s[i+1..j-1] is one, or the piece has at most 2 letters.

Trying end from the last index down gives sorted output. Two splits with different first pieces agree up to the end of the shorter piece; there the shorter has | and the longer has a letter, so the longer first piece sorts first.

Algorithm

Fill pal[i][j] for i from n-1 down to 0: s[i] == s[j] and either j-i < 2 or pal[i+1][j-1].
Write backtrack(start). If start equals n, join the current pieces with | and save the string.
Otherwise loop end from n-1 down to start, and skip it unless pal[start][end].
Add s[start..end] to the pieces, call backtrack(end+1), then remove the piece.
Call backtrack(0) and return the saved splits, already sorted.

def partition(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways.
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    result = []
    parts = []

    def backtrack(start):
        if start == n:
            result.append("|".join(parts))
            return
        # Longest piece first: "|" sorts after every letter, so a longer
        # first piece gives a smaller string and the output stays sorted.
        for end in range(n - 1, start - 1, -1):
            if pal[start][end]:
                parts.append(s[start:end + 1])
                backtrack(end + 1)
                parts.pop()

    backtrack(0)
    return result

Pitfalls and edge cases

Trying the shortest piece first. The splits are right but the order is wrong: a|a|b before aa|b.
Sorting at the end with a comparison that follows language or locale rules, which can put | before the letters. Compare character codes, or generate the splits in order.
Filling the palindrome table with i going up. pal[i+1][j-1] is then read before it is computed; fill i from n-1 down.
Mixing an inclusive end with an exclusive substring end. The piece s[start..end] has end-start+1 letters.
Saving the shared list of pieces instead of the joined string. The search keeps changing that list, so every saved entry ends up the same.

Frequently asked questions3

What is the time complexity of Palindrome Partitioning?

On a string of equal letters all 2^(n-1) splits are answers, each up to 2n-1 characters long: O(n × 2^n). No method beats that, because writing the answer costs as much. The palindrome table adds O(n²) time and space, and the recursion O(n).

How many palindrome partitions can a string have?

At most 2^(n-1), one for each way to choose which of the n-1 gaps to cut. A string of equal letters reaches that bound: 1,024 splits for 11 letters. A string with no repeated letters has exactly one split, every letter on its own.

Is Palindrome Partitioning dynamic programming or backtracking?

It uses both. Listing up to 2^(n-1) splits takes a search that builds each split piece by piece: backtracking. Dynamic programming supplies the yes or no table of palindromic substrings that the search reads, filled once in O(n²).