Palindrome partitioning and minimum cuts in Python

Why this matters

A palindrome is a word that reads the same forwards and backwards, such as level or noon. Palindrome partitioning asks you to split a string into pieces so that every piece is a palindrome. The question is how few splits you can make.

This problem combines two ideas from earlier in the module. The memoization and tabulation lesson showed how to store answers to smaller problems and reuse them. The palindromic substrings lesson showed how to check whether a piece is a palindrome. Here both ideas meet. A table answers "is this piece a palindrome?" in one lookup, and a second list answers "what is the fewest cuts for this prefix?" in one lookup.

Every program here is a plain Python file. The programs marked python run print their output without reading input. Run any file with python3 main.py. The outputs shown were produced on Python 3.14.

The problem

A cut is a place between two letters where you split the string. The string aab has two possible cut places: between the first and second letters, and between the second and third letters.

• A cut after the first letter gives a and ab. The piece ab is not a palindrome, so this split fails.
• A cut after the second letter gives aa and b. Both pieces are palindromes, so this split works.
• No cut at all gives aab, which is not a palindrome.

The fewest cuts that work is 1. The task is to find that number for any string, and to find a list of the pieces too.

Step 1: Check whether each substring is a palindrome

Before choosing cuts, you need to know which substrings are palindromes. A substring is a piece of the string that starts at position i and ends at position j, counting from 0. The letter at i is the first letter and the letter at j is the last letter. In Python, s[i] gives the letter at a position.

A substring from i to j is a palindrome when two things are true.

1. The first letter and the last letter are the same.
2. The substring between them, from i + 1 to j - 1, is a palindrome too. Two letters with nothing between them count as a palindrome, and so does a single letter.

Storing the answer for every pair (i, j) in a two-dimensional list makes this check a lookup. Each cell starts as False.

Here is the table for aab, where True means the substring from row i to column j is a palindrome:

isPal   j=0    j=1    j=2
i=0     True   True   False
i=1     -      True   False
i=2     -      -      True

Cells below the diagonal are not used, so they are left as -. The cell for i=0, j=1 is True because aa is a palindrome. The cell for i=0, j=2 is False because aab is not.

The table has to be filled in a specific order. To decide cell (i, j), you need cell (i + 1, j - 1), which is one row lower. So the loop over i runs from the last row up to the first. The range(n - 1, -1, -1) in Python counts down from n - 1 to 0.

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True
    return is_pal

The condition j - i < 2 covers two cases. When j equals i, the piece is a single letter, which is always a palindrome. When j is i + 1, the piece has two letters, and it is a palindrome when they match. In both cases there is no inner part to check. Python's and and or stop as soon as the answer is known. So when j - i < 2 is true, the lookup is_pal[i + 1][j - 1] is skipped.

Step 2: Build the cut list

Now the cuts. Define cut[i] as the fewest cuts needed to split the prefix that ends at position i. The prefix is the piece from position 0 up to i, including i.

Two rules fill the list.

1. If the whole prefix from 0 to i is a palindrome, no cut is needed, so cut[i] is 0.
2. Otherwise, pick a last piece that starts at some position j, where j is between 1 and i. The last piece runs from j to i, so it must be a palindrome. The text before it is the prefix ending at j - 1, which has already been solved and stored in cut[j - 1]. Adding one more cut for the boundary before j gives cut[j - 1] + 1. Try every valid j and keep the smallest value.

The answer for the full string is cut[n - 1].

cut = [0] * n
for i in range(n):
    if is_pal[0][i]:
        cut[i] = 0
        continue
    best = float("inf")
    for j in range(1, i + 1):
        if is_pal[j][i]:
            best = min(best, cut[j - 1] + 1)
    cut[i] = best

float("inf") is Python's way to write a number bigger than any real answer. It plays the same role as Java's Integer.MAX_VALUE. The function min returns the smaller of its arguments. Every position has at least one valid last piece, the single letter at that position, so no value in cut stays at infinity.

This is tabulation in the same style as the earlier lessons. Each cut[i] depends only on smaller positions, so the loop fills the list from left to right, and each value is ready before it is used.

Worked example 1: aab

Start with the table from Step 1. Then fill the cut list one position at a time.

i    prefix    isPal[0][i]    best choice                      cut[i]
0    a         True           whole prefix is a palindrome     0
1    aa        True           whole prefix is a palindrome     0
2    aab       False          j=2 gives piece b, cut[1] + 1    1

For i = 2, the whole prefix aab is not a palindrome. The only valid last piece that is a palindrome is b, which starts at j = 2. The prefix before it is aa, and cut[1] is 0. So cut[2] = 0 + 1 = 1.

The answer is cut[2], which is 1.

Step 3: The full program with the list of pieces

A number of cuts is useful, but a program that tells you where to cut is more useful. Store one extra list, start, that records where the last piece begins for each prefix. Then walk backwards from the end of the string to rebuild the pieces.

Pieces are found from the end, so the list of pieces needs reversing before it is printed. The method result.reverse() does that in place.

The program below puts the table, the cut list and the rebuild step together. It runs the examples from this lesson and a few more. It does not read input.

The output is:

aab -> cuts=1 pieces=['aa', 'b']
a -> cuts=0 pieces=['a']
ab -> cuts=1 pieces=['a', 'b']
racecar -> cuts=0 pieces=['racecar']
abccbc -> cuts=2 pieces=['a', 'bccb', 'c']
abacdcaba -> cuts=0 pieces=['abacdcaba']
abcde -> cuts=4 pieces=['a', 'b', 'c', 'd', 'e']
aaaa -> cuts=0 pieces=['aaaa']
abcba -> cuts=0 pieces=['abcba']
noonabbad -> cuts=2 pieces=['noon', 'abba', 'd']
level -> cuts=0 pieces=['level']
ababbbabbababa -> cuts=3 pieces=['a', 'bab', 'bbabb', 'ababa']

The racecar and abacdcaba lines show a string that is already a palindrome, which needs 0 cuts. The abcde line shows the other extreme. No two neighbouring letters match, so every letter must be its own piece, which takes 4 cuts for 5 letters.

The slice s[frm:end + 1] includes both ends. In Python, a slice s[a:b] includes a and stops before b. To include the letter at end, the second number has to be end + 1.

Worked example 2: abccbc

This example is harder because the best answer is not obvious at a glance. Read the string as a, bccb, c. The first and last pieces are single letters. The middle piece bccb reads the same backwards, so it is a palindrome. That makes 2 cuts.

The program finds the same split. For i = 5, the whole prefix abccbc is not a palindrome, so the program looks at every palindrome that ends at position 5. Those are cbc (starting at j = 3) and c (starting at j = 5). The first one needs cut[2] + 1 = 3 and the second needs cut[4] + 1 = 2, so the second wins. Here is the full trace of the cut list.

i    prefix      isPal[0][i]   best (j, value)           cut[i]
0    a           True          none needed               0
1    ab          False         j=1 piece b, cut[0] + 1   1
2    abc         False         j=2 piece c, cut[1] + 1   2
3    abcc        False         j=2 piece cc, cut[1] + 1  2
4    abccb       False         j=1 piece bccb, cut[0] + 1 1
5    abccbc      False         j=5 piece c, cut[4] + 1   2

At i = 4 the prefix abccb is cut as a and bccb, so cut[4] is 1. At i = 5 the last piece is the single letter c at j = 5. The value is cut[4] + 1 = 2. The answer is 2, which matches the output above.

Worked example 3: ababbbabbababa

This example is the hardest of the three. It has 14 letters and a longer palindrome in the middle. The program gives the answer 3 with these pieces.

a | bab | bbabb | ababa

Check each piece by reading it forwards and backwards. a is one letter. bab reads the same both ways. bbabb reads the same both ways. ababa reads the same both ways. There are 3 cuts because 4 pieces need 3 gaps between them.

Why not 2 cuts? The cut list already checked that case. Its last value, cut[13], is the fewest cuts over all ways to split the string, and it is 3.

The method was also checked against a brute force search on 2000 random strings of up to 9 letters, with a fixed seed. The brute force tries every set of cut positions and keeps the smallest count that gives only palindromes. The two methods gave the same answer on every string.

Common mistakes

The first mistake is filling the palindrome table from the top row down. This gives a wrong answer that is hard to notice, because the table looks plausible. Here is the table loop with the outer loop running the wrong way.

def bad_table(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True
    return is_pal

With this order, is_pal[i + 1][j - 1] is read before row i + 1 has been filled, so it is still False. On the input aba, the substring aba is marked as not a palindrome. The next program runs the bad table and the cut list on aba.

The output is:

isPal[0][2] for aba, ascending fill: False
cuts for aba with bad table: 2
cuts for aba with correct table: 0

The correct answer for aba is 0, because the whole string is a palindrome. The bad table gives 2.

The second mistake is removing the check for a whole palindromic prefix. Without that check, the cut list always looks for a last piece that starts after position 0, so the first prefix has no way to be split and its value stays at infinity. Every later value that reads it stays at infinity too. For aa, the answer then prints inf instead of 0. The fix is the first rule in Step 2, which sets cut[i] to 0 when the whole prefix is a palindrome.

The third mistake is a missing length check. The table code reads is_pal[i + 1][j - 1], and a list index past its end raises an error. For a single letter, where i and j are the same, the index i + 1 can run past the end of the list. The program below leaves out the j - i < 2 check and runs on the input a.

def bad_len(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and is_pal[i + 1][j - 1]:
                is_pal[i][j] = True
    return is_pal
 
 
bad_len("a")

Python stops with this error:

IndexError: list index out of range

The message says the program tried to read a position that is not in the list. Here i + 1 is 1, and the outer list has length 1. The fix is the j - i < 2 check, placed before the lookup.

The fourth mistake is forgetting that a slice stops before its second number. Writing s[frm:end] drops the last letter of every piece, because end is the position of the last letter, not the position after it. For aab, the pieces come out as 'a' and an empty string, instead of 'aa' and 'b'. The number of cuts is still computed from the table, so min_cuts gives the right number, which makes this bug easy to miss. Check the pieces list as well as the number.

Practice

Try each exercise before reading its answer.

Exercise 1. Find min_cuts("abc") and the pieces, by hand and then by running the program.

Show the answer

min_cuts("abc") is 2. The pieces are a, b and c. No two neighbouring letters are the same, and no longer piece is a palindrome, so every letter has to stand alone.

Exercise 2. Find min_cuts("aabbaa") and explain why the answer is 0 without building any table.

Show the answer

The answer is 0. Reading the string forwards gives aabbaa, and reading it backwards gives aabbaa. The whole string is already a palindrome, so no cut is needed. The program reaches the same answer because is_pal[0][5] is True, which triggers the first rule for the cut list.

Exercise 3. Find min_cuts("cdd") and the pieces.

Show the answer

min_cuts("cdd") is 1, with the pieces c and dd. The string cdd is not a palindrome. The cut after the first letter gives c, a palindrome, and dd, also a palindrome.

Exercise 4. Explain why the outer loop of build_palindrome_table runs from n - 1 down to 0, and not from 0 up to n - 1.

Show the answer

Cell is_pal[i][j] depends on cell is_pal[i + 1][j - 1], which is in row i + 1. If the loop started at row 0, row i + 1 would not be filled when row i is decided, so the lookup would read False. Starting at the bottom row means every row that a cell depends on is already done. The wrong order is shown in the mistakes section above.

Exercise 5. Change min_cuts so it returns the number of pieces instead of the number of cuts. Check the answer on aab, which should give 2.

Show the answer

Each piece needs one cut before it except the first, so the number of pieces is the number of cuts plus 1. For an empty string the answer is 0. The change is in the return statement:

return cut[n - 1] + 1

The n == 0 check stays as it is, because it returns before this line. On aab, cut[2] is 1, so the new return value is 2, which matches the two pieces aa and b.

Summary

• A palindrome table stores, for each pair of positions (i, j), whether the substring between them is a palindrome.
• The table is filled from the bottom row up, because each cell depends on the cell one row lower.
• The cut list stores the fewest cuts for each prefix. A prefix that is a palindrome needs 0 cuts.
• Otherwise, try each possible start j for the last piece and keep the smallest cut[j - 1] + 1.
• A second list that records where each last piece starts lets the program rebuild the pieces.
• The table has one cell for each pair of positions, so a string of 2,000 letters needs 4 million cells.