Minimum Palindrome Partitions

December 14, 2019

A cut is defined as a slice of a string that par­ti­tions a string into two. Given a string, return the min­i­mum number of cuts required to par­ti­tion the string into palin­dromic sub­strings.

Some exam­ples:

a would return 0, since a is already a palin­drome and no cuts are required.

asa would also return 0, since asa is also a palin­drome.

as would return 1, since one cut is required: a|s.

aasaadl would return 2: aasaa|d|l.

The solu­tion is a bril­liant usage of dynam­ic pro­gram­ming - one of those times where you’re com­plete­ly stuck at first but seems so obvi­ous once you know it.

What we’re mem­o­iz­ing is the number of cuts required for each of the pre­fix­es, and run­ning mid-point checks from each of the start­ing points (not for­get­ting to take both odd and even length palin­dromes into account). Run­ning time is qua­drat­ic in the length of the string, and space required is linear.

min-palindrome-partitions
Memoizing palindrome partitions.

As you can see, when we detect a palin­drome, we update the cuts array with a pre­vi­ous value of cuts (which we already know to be opti­mal) + 1.

def minimum_palindrome_partitions(s):
    # cuts[i] = how many palindrome partitions required to cut s[:i]
    # we initialize it as i-1 first since that's the maximum number of cuts possibly required (if all characters are distinct)
    cuts = [i-1 for i in range(len(s) + 1)]
    # check each center of palindrome candidate
    for i in range(len(s)):
        # at each center, check odd length palindromes
        for j in range(min(i + 1, len(s) - i)):
            if s[i - j] == s[i + j]:
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j] + 1)
            else:
                break
        # at each center, check even length palindromes
        for j in range(min(i, len(s) - i)):
            if s[i - j - 1] == s[i + j]:
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j - 1] + 1)
            else:
                break
    return cuts[-1]