1
class Solution:
2
    def isPallindrom(self, s: str, l, r) -> bool:
3
        st = s[l : r + 1]
4
        rev = st[::-1]
5
        return st == rev
6

7
    def minCut(self, s: str) -> int:
8
        N = len(s)
9
        if not s:
10
            return 0
11
        if self.isPallindrom(s, 0, N - 1):
12
            return 0
13
        dp = [sys.maxsize] * (N + 1)
14
        dp[-1] = 0
15

16
        for i in range(N - 1, -1, -1):
17
            for j in range(i, N):
18
                if self.isPallindrom(s, i, j):
19
                    dp[i] = min(dp[i], 1 + dp[j + 1])
20

21
        return dp[0] - 1