# 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.

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]``````