# Question

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.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.


# Solution

Use Dynamic Programming to store the minimum cuts needed up to an index, i.e. dp[i] is the mininum number of cuts for s[:i+1]. From each index, evaluate palimdrones centered at it (for odd-length palimdrones) or between it and its right neighbor (for even length palimdrones) to minimize number of passes needed for palindromes. Do not forget to evaluate a single-character palimdrone for odd-length ones.

class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
length = len(s)
cuts = [i for i in range(length)]

for i in range(length):
# Odd size palindrome
j = 0 # one-character palindrome when j == 0
while i - j >= 0 and i + j < length and s[i - j] == s[i + j]:
prev_cuts = cuts[i - j - 1] if i - j - 1 >= 0 else -1
cuts[i + j] = min(cuts[i + j], prev_cuts + 1)
j += 1

# Even size palindrome
j = 0
while i - j >= 0 and i + j + 1 < length and s[i - j] == s[i + j + 1]:
prev_cuts = cuts[i - j - 1] if i - j - 1 >= 0 else -1
cuts[i + j + 1] = min(cuts[i + j + 1], prev_cuts + 1)
j += 1

return cuts[-1]