Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”, return 1 since the palindrome partitioning [“aa”,“b”] could be produced using 1 cut.

Analysis

The first thing we need to do is write a function that is able to determine when a string is a palindrome. A palindrome is a string that reads the same from left to right as from right to left. Therefore, a simple way to test whether a string is a palindrome is to loop over every character in the string and compare it to the string at the same position from the other end. For example, if we have the string “madam”, we start by looking at the first character, m, and comparing it to the last character, which is also m. Since they are equal, we continue and look at the second character, a, and compare it to the second-to-last character, in this case also m. We continue in this fashion either until we find a pair of characters that is not equal, in which case we return false (not a palindrome), or when we reach the middle of the string, in which case we return true. Here is an implementation of this algorithm in Go:

func IsPalindrome(s string) bool {
    // convert to rune to account for non-ascii strings
    r := []rune(s)
    ln := len(r)
    for i := 0; i < ln/2; i++ {
        if r[i] != r[ln-i-1] {
            return false
        }
    }
    return true
}

Now that we have a function for determining whether a string is palindromic, we can get to the crux of the problem. We desire an algorithm that is able to find the minimum number of cuts we need to make to a string to turn all its parts into palindromes.

First, let us consider the brute force solution. This would be to attempt every possible partitioning, and then storing the number of cuts made if it is smaller than any previous number we have found and all the partitions are palindromes. There are N-1 positions where we can cut the string, and we need to consider every combination of these positions.

For the string abcd, for example, we can cut it in 3 different positions at once: a|b|c|d. We can also cut two at a time: a|b|cd, a|bc|d, ab|c|d, or one at a time: a|bcd, ab|cd, abc|d, or no cuts at all, for a total of 8 combinations. In general, it is possible to prove that there are 2^N possible partitionings for a string of length N. So the complexity of the brute force solution will be O(N.2^N), because we will need to check every partitioning (2^N combinations), and for each partitioning whether every partition is a palindrome (checking N characters in total, worst case). O(N.2^N) is not very good, and we can do better. Let’s try to find a more efficient solution.

As a rule of thumb, whenever a problem requires us to find the “minimum” or “maximum”, a dynamic programming solution should be considered early on. Let us see if we can formulate this problem in a way that leans itself to a DP solution. We start by looking at a section of the full string, from index i to j. If the string from i to j is palindromic, we don’t need any more cuts, and the answer is 0. Otherwise we need at least one cut, and the total minimum number of cuts needed to make this section palindromic will be one plus the minimum number of cuts needed to make the two new subsections palindromic. In mathematical notation, it looks like this:

f(i,j) = \begin{cases}
        min[f(i,k)+f(k+1,j) + 1 \mbox{ for } i \leq k \lt j]& \mbox{if }str[i:j] \mbox{ is not a palindrome}\\
        0& \mbox{otherwise}
        \end{cases}

You will notice that this definition is recursive, which is why it is a dynamic programming solution. We break the string up into smaller subsections, and apply the same algorithm on those substrings. If we implement this as a recursive solution however, the time complexity will be polynomial on the length of the string, which will be unacceptably slow for longer strings. We can instead build a NxN matrix of values calculated up to that point, and solve the problem in O(N^2) time and O(N^2) space. The matrix will be filled from the diagonal outwards, so that the final solution will reside in the corner of the matrix.

For example, if we have the string “abbaa”, the matrix will look like this:

[0 1 1 0 1]
[0 0 0 1 1]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 0 0 0]

The zeroes on the diagonal represent the fact that the string from index i to i+1 will always be palindromic, because it’s only one character long. At index 0, 4 we have a value of zero again, because s[0:4] (“abba”) is palindromic. The minimum number of cuts is therefore 1, at index 4.

Solution

The following solution is implemented in Go:

func MinPalindromeCuts(s string) int {
    // convert to rune to account for non-ascii strings
    r := []rune(s)
    l := len(r)

    table := make([][]int, l)
    for i := range table {
        table[i] = make([]int, l)
    }

    for u := 1; u <= l; u++ {
        for y := l - u; y >= 0; y-- {
            i := l - u - y
            j := i + u - 1
            if IsPalindrome(string(r[i : j+1])) {
                table[i][j] = 0
            } else {
                minCuts := 1 << 7 - 1
                for k := i; k < j; k++ {

                    m := table[i][k] + table[k+1][j] + 1
                    if m < minCuts {
                        minCuts = m
                    }
                }
                table[i][j] = minCuts
            }
        }
    }

    return table[0][l-1]
}

Follow-up questions

What is the time complexity of the solution?

The solution runs in O(N^3) time: there are two loops present in the main function, and they run the IsPalindrome function, which is itself O(N). Therefore, the solution is O(N^3).

How would you improve upon the solution above? (Hint: the solution can be improved both in terms of efficiency and in terms of memory usage)

One quick optimization we can make is to check, at the start of the function, whether the full string is already a palindrome. If it is, we can immediately return 0 for a total cost of O(N), the cost of checking that the string is a palindrome.

We can improve the solution further by noting that a substring str[a:b] is only a palindrome if the characters at a and b are equal, and str[a+1:b-1] is also a palindrome. We may therefore build an NxN table to store whether every substring of str is a palindrome or not. We could do this during preprocessing at a cost of O(N^2), and then use this table during our main function execution to do lookups in O(1), which brings the total time complexity down to O(N^2).

If memory constraints are tight, we may also improve on the solution above by using a one-dimensional array instead of a 2D array. This removes some of the memory overhead of storing separate arrays.