Palindrome partitioning and minimum cuts

Why this matters

Text tools often split a long string into pieces that each read the same forwards and backwards. A tool that checks a DNA string for mirror-like stretches does this. So does a tool that breaks a long word list into parts. Each piece must be checked, and the number of ways to cut a string grows very fast. Trying every way by hand is too slow once the string has more than a few dozen letters.

This lesson answers one question. Given a string, what is the fewest number of cuts that split it into palindromes? The method is dynamic programming. That means solving the small versions of the problem first, saving each answer in a table, and reading the saved answers when a bigger version needs them. The earlier lesson on palindromic substrings showed how to find palindromes by expanding around centres. This lesson stores every palindrome check in a table, so the cut count can be built from those checks.

Palindromes and cuts in plain words

A palindrome is a string that reads the same from left to right and from right to left. racecar is a palindrome. noon is one too. abc is not, because it reads cba backwards. A single letter counts as a palindrome. So does aa.

A cut is a place between two neighbouring letters where we split the string. Picture a strip of paper with letters written on it, and a pair of scissors. Each snip is a cut. A string of 3 letters has 2 gaps between letters, so it has 2 possible places to cut. A string of length n has n - 1 gaps.

Take the string aab. It has two gaps. The gap between the two a letters gives the pieces aa and b. Both are palindromes. That is one cut. Cutting nothing leaves aab, which is not a palindrome. So the fewest cuts for aab is 1.

The worst case is easy to see. If you cut every gap, every piece is one letter, and one letter is always a palindrome. So the answer is never more than n - 1. The job is to find the smallest answer, which is often much less.

The first check: is the whole string a palindrome?

If the whole string is a palindrome, the answer is 0 cuts. Nothing needs to be split. For racecar the answer is 0.

If the whole string is not a palindrome, we must cut. The question is where. The rest of this lesson builds a method that tries every useful place and keeps the best.

To talk about parts of a string, we use positions. Positions start at 0 in C++. The string aab has positions 0, 1 and 2. The part of the string from position i to position j, with both ends included, is written s[i..j]. For example, s[1..2] in aab is ab.

Step 1: a table that says which parts are palindromes

We build a table called isPal. The entry isPal[i][j] is true when s[i..j] is a palindrome, and false when it is not. A table like this is a 2D grid. In C++ we store it as a vector of vectors, so isPal[i][j] is the cell in row i and column j.

For aab the table has these values:

Only the cells where i is less than or equal to j matter, because s[i..j] is empty or reversed otherwise. The cell isPal[0][1] is true because aa is a palindrome. The cell isPal[1][2] is false because ab is not.

We fill the table with three rules:

• A single letter is always a palindrome. So isPal[i][i] is true.
• Two letters are a palindrome when they are equal. So isPal[i][i + 1] is true when s[i] equals s[i + 1].
• A longer part is a palindrome when its two outer letters are equal and the part inside them is also a palindrome. So isPal[i][j] is true when s[i] equals s[j] and isPal[i + 1][j - 1] is true.

The third rule needs the answer for a shorter part, the one inside. So we fill the table by length. First all the single letters, then all the pairs, then all the parts of length 3, and so on. When we reach a part of length 5, every shorter part is already done.

This is the central habit of dynamic programming. A bigger answer is built from smaller answers, so the small ones must be ready first. Filling the table in the wrong order gives wrong answers. If a longer part is checked before the part inside it is filled in, the inside still holds its starting value, which is false. The longer part is then wrongly marked as not a palindrome.

Here is the code that fills the table. The variable len is the length of the part being checked.

std::vector<std::vector<bool>> isPal(n, std::vector<bool>(n, false));
for (int i = 0; i < n; ++i) isPal[i][i] = true;
for (int len = 2; len <= n; ++len) {
    for (int i = 0; i + len - 1 < n; ++i) {
        int j = i + len - 1;
        isPal[i][j] = s[i] == s[j] && (len == 2 || isPal[i + 1][j - 1]);
    }
}

The check len == 2 is there for a reason. When the part has length 2, the inside from i + 1 to j - 1 is empty. An empty inside has no letters to compare, so the test is just whether the two outer letters match. Without the check, the code would read isPal[i + 1][i]. That cell is in range, but it is never filled, so it stays false. Then every pair of equal letters, such as aa, would be marked as not a palindrome.

The loop condition i + len - 1 < n keeps j inside the string. The part from i to j has length j - i + 1, which equals len when j is i + len - 1. So for each length we try each starting position i that still leaves room for a part of that length.

Step 2: the cut array

The table tells us which parts are palindromes. The second table, called cuts, tells us the fewest cuts for each prefix of the string. A prefix is the part from the start of the string up to some position. The prefix s[0..i] is the first i + 1 letters.

The entry cuts[i] is the fewest cuts that split the prefix s[0..i] into palindromes. The answer for the whole string is cuts[n - 1], because s[0..n - 1] is the whole string.

There are two cases for each i.

Case 1: the prefix is a palindrome. Then no cut is needed, and cuts[i] is 0.

Case 2: the prefix is not a palindrome. Then at least one cut is needed. Look at the last piece. It starts at some position j, where j is between 1 and i. The last piece is s[j..i]. This piece must be a palindrome, so we check isPal[j][i]. If it is a palindrome, the rest of the prefix is s[0..j - 1], which we have already solved, and its answer is cuts[j - 1]. Putting one more cut before position j gives cuts[j - 1] + 1 cuts. We try every valid j and keep the smallest result.

The recurrence, which is the rule that fills the table, is this:

cuts[i] = 0                               if isPal[0][i]
cuts[i] = min over j of cuts[j - 1] + 1  for each j from 1 to i where isPal[j][i]

Notice that the rule reads cuts[j - 1], which is a prefix shorter than the current one. So the cut array is also filled from left to right, one prefix at a time.

Here is the cut array for aab, step by step:

For i = 2 the code also tries j = 1. That would make the last piece ab, which is not a palindrome, so it is skipped. The only valid choice is j = 2. The answer is cuts[2], which is 1.

The full program

The program below has three parts. The function minCuts returns the number of cuts. The function pieces returns the pieces themselves, which is useful when you need the split and not only the count. The main function runs both on a few strings.

#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
 
// Returns the fewest cuts that split s into palindromes.
int minCuts(const std::string& s) {
    int n = static_cast<int>(s.size());
    if (n == 0) return 0;
 
    // isPal[i][j] is true when s[i..j] (both ends included) is a palindrome.
    std::vector<std::vector<bool>> isPal(n, std::vector<bool>(n, false));
    for (int i = 0; i < n; ++i) isPal[i][i] = true;
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            isPal[i][j] = s[i] == s[j] && (len == 2 || isPal[i + 1][j - 1]);
        }
    }
 
    // cuts[i] is the fewest cuts that split the prefix s[0..i].
    std::vector<int> cuts(n, 0);
    for (int i = 0; i < n; ++i) {
        if (isPal[0][i]) continue;  // whole prefix is one piece: cuts[i] stays 0
        cuts[i] = INT_MAX;
        for (int j = 1; j <= i; ++j) {
            if (isPal[j][i]) cuts[i] = std::min(cuts[i], cuts[j - 1] + 1);
        }
    }
    return cuts[n - 1];
}
 
// Returns the pieces themselves, in order.
std::vector<std::string> pieces(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<std::vector<bool>> isPal(n, std::vector<bool>(n, false));
    for (int i = 0; i < n; ++i) isPal[i][i] = true;
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            isPal[i][j] = s[i] == s[j] && (len == 2 || isPal[i + 1][j - 1]);
        }
    }
 
    std::vector<int> cuts(n, 0);
    std::vector<int> start(n, 0);  // where the last piece of the best split begins
    for (int i = 0; i < n; ++i) {
        if (isPal[0][i]) continue;  // whole prefix is one piece
        cuts[i] = INT_MAX;
        for (int j = 1; j <= i; ++j) {
            if (isPal[j][i] && cuts[j - 1] + 1 < cuts[i]) {
                cuts[i] = cuts[j - 1] + 1;
                start[i] = j;
            }
        }
    }
 
    std::vector<std::string> out;
    int end = n - 1;
    while (end >= 0) {
        int from = isPal[0][end] ? 0 : start[end];
        out.push_back(s.substr(from, end - from + 1));
        end = from - 1;
    }
    std::reverse(out.begin(), out.end());
    return out;
}
 
int main() {
    for (std::string s : {"aab", "ab", "abccbc", "aabbbaa", "abc"}) {
        std::cout << s << ": " << minCuts(s) << " cut(s), pieces";
        for (const auto& p : pieces(s)) std::cout << " [" << p << "]";
        std::cout << "\n";
    }
}

The variable start[i] is new in pieces. It records the place where the last piece begins in the best split of the prefix. When isPal[0][i] is true, the whole prefix is one piece, so start[i] stays 0.

The loop that builds the answer walks backwards from the end of the string. It takes the piece that ends at end, then jumps to the piece before it. The loop stops when end is below 0. Then reverse puts the pieces in their original order.

The function uses INT_MAX from <climits> as a starting value that any real count beats. Every prefix can be cut into single letters, so each cuts[i] ends up as a real count, never INT_MAX. That means cuts[j - 1] + 1 is never added to INT_MAX, so there is no overflow.

Running the program

Save the program above as pal_final.cpp. Compile with the warning flags turned on. Each command below is run from the folder that holds the file.

g++ -std=c++20 -Wall -Wextra -o pal_final pal_final.cpp
./pal_final

The output is:

aab: 1 cut(s), pieces [aa] [b]
ab: 1 cut(s), pieces [a] [b]
abccbc: 2 cut(s), pieces [a] [bccb] [c]
aabbbaa: 0 cut(s), pieces [aabbbaa]
abc: 2 cut(s), pieces [a] [b] [c]

The compiler printed no warnings. The result for aab matches the hand trace above. The result for abc is 2, because ab and bc are not palindromes, and the only valid split is three single letters.

A second example: abccbc

The string abccbc is longer and has more choices. Here is the cut array, traced by hand. Each row shows the best last piece that was found.

Row 4 is the interesting one. The prefix abccb is not a palindrome, but the piece bccb from position 1 is. Everything before it is a, which costs 0 cuts. So the total is one cut. That is a better answer than cutting every letter.

Row 5 shows that the best answer does not have to come from the piece nearest the end. The piece cbc from position 3 is a palindrome, and it gives cuts[2] + 1 = 3. The piece c from position 5 gives cuts[4] + 1 = 2, which is better. The minimum is taken over all the choices.

The final answer is cuts[5] = 2. The pieces are a, bccb and c, which is the output the program printed.

A third example: printing the pieces

Sometimes the caller needs the pieces, not just the count. The start array makes that possible. For each prefix, start[i] stores where the last piece of the best split begins. To print the pieces, start at the end of the string and step backwards.

For abccbc, the walk goes like this:

• end is 5. The table says start[5] is 5, so the last piece is s[5..5], which is c. The next end is 4.
• end is 4. The table says start[4] is 1, so the piece is s[1..4], which is bccb. The next end is 0.
• end is 0. The prefix s[0..0] is a palindrome, so the piece is s[0..0], which is a. The next end is -1, and the walk stops.

The pieces were found from last to first, so reverse puts them in order: a, bccb, c.

Cost: time and memory

Filling the isPal table checks each pair i and j with i <= j once. That is about n * n / 2 checks, and each check is a constant amount of work. Filling the cuts array tries up to i values of j for each i, which is also about n * n / 2 steps. So the total time is O(n squared). Here O(n squared) means the work grows with the square of the string length. Doubling the length makes the work about four times as large.

The isPal table stores one value for each pair of positions. A vector<bool> stores each value in one bit. For a string of 2,000 letters, the table has about 4 million cells, which takes about 0.5 MB. The cuts and start arrays take only one number per letter. For a string of 20,000 letters the table would need about 50 MB, so the method is best for strings up to a few thousand letters.

Common mistakes

Counting pieces instead of cuts

One cut makes two pieces. A split into 3 pieces needs 2 cuts. The number the function returns is the cut count, which is one less than the piece count. The program's pieces function gives the pieces, so you can check the count by hand: aab gives the pieces [aa] [b], which is 2 pieces and 1 cut.

Using the wrong index for the previous cut count

The cut that separates the last piece sits right before position j. The number of cuts for the part before that cut is cuts[j - 1], not cuts[j]. The entry cuts[j] covers the prefix that includes the piece starting at j, so using it would count the piece's own letters as if they were already split.

Forgetting the base case for pairs

As shown above, the check len == 2 prevents aa from being marked as not a palindrome. If you leave the check out, the code still compiles and runs, but the table is wrong. For aa the answer becomes 1 instead of 0, because aa is never marked as a palindrome. Test a string made of two equal letters.

Filling the table in the wrong order

The table must be complete for shorter parts before a longer part reads it. Filling isPal with the starting position i counting up from 0 reads row i + 1 before that row is filled in. Filling by length, as the code does, avoids this.

Signed and unsigned comparisons

A common slip is looping with an int index over std::string::size(), which returns an unsigned number. Compiling a small test file with -Wall gives this real warning:

mistakes.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < s.size(); ++i) std::cout << s[i];

The fix is to convert the size once, as the program does with static_cast<int>(s.size()), and then use int everywhere in the loops.

Practice

Exercise 1

Find the fewest cuts for abc and for aaa by hand. Then check your answers with the program.

Show the answer

For abc the answer is 2. The pieces are a, b and c, because no two neighbouring letters form a palindrome. For aaa the answer is 0, because the whole string is a palindrome.

Exercise 2

Fill in the cuts array for the string abbc. Use the rule that cuts[i] is 0 when the prefix is a palindrome, and otherwise the smallest cuts[j - 1] + 1 over the valid j.

Show the answer

The array is 0, 1, 1, 2. For abb, the piece bb starts at j = 1, so cuts[0] + 1 = 1. For abbc, the piece c starts at j = 3, so cuts[2] + 1 = 2. The piece bbc is not a palindrome, and the piece bc is not one either, so they are skipped.

Exercise 3

Explain in your own words why the recurrence uses cuts[j - 1] + 1 and not cuts[j] + 1.

Show the answer

The cut goes just before position j, so the part before the cut is the prefix that ends at j - 1. Its answer is cuts[j - 1]. The entry cuts[j] would include the last piece, so it would not describe the part before the cut.

Exercise 4

Show that the answer for any string of length n is never more than n - 1.

Show the answer

Cutting at every gap between letters gives n pieces that each hold one letter. A single letter is a palindrome, so this split is valid. It uses n - 1 cuts, which is an upper bound. The minimum is at most this number.

Exercise 5

Change main so that it prints the pieces of racecar, noon and abcba. Predict the output before you run it.

Show the answer

Each of these strings is a palindrome, so each one is a single piece. The output is racecar: 0 cut(s), pieces [racecar], and the same pattern for noon and abcba. The start array is never used, because isPal[0][n - 1] is true for each string.

Summary

• A palindrome reads the same both ways. A cut is a split between two neighbouring letters.
• The table isPal[i][j] is filled by length, so each longer part reads answers for shorter parts that are already known.
• The array cuts[i] holds the fewest cuts for the prefix ending at i. It is 0 when the prefix is a palindrome, and otherwise the smallest cuts[j - 1] + 1 over valid last pieces.
• The answer for the whole string is cuts[n - 1], which is the number of pieces minus one.
• Storing the start of the last piece in each step lets the program print the pieces.
• The method takes O(n squared) time and memory, so it suits strings up to a few thousand letters.