```
class Solution(object):
def minCut(self, s):
n = len(s)
def update_cuts(left, right):
while 0 <= left <= right < n and s[left] == s[right]:
# Either include a new palindrome with one additional cut or not.
cuts[1 + right] = min(cuts[1 + right], 1 + cuts[left])
left -= 1
right += 1
cuts = [i - 1 for i in range(n + 1)]
for i in range(n):
left, right = i, i
update_cuts(left, right)
left, right = i, i + 1
update_cuts(left, right)
return cuts[-1]
```