1function MinCuts(s):
2 n = s.length
3 isPal = array[n][n] fill false
4 dp = array[n] fill 0
5
6 # 1. Precompute palindromes
7 for len = 1 to n:
8 for i = 0 to n - len:
9 j = i + len - 1
10 if s[i] == s[j] and (len <= 2 or isPal[i+1][j-1]):
11 isPal[i][j] = true
12
13 # 2. Find min cuts
14 for i = 0 to n-1:
15 if isPal[0][i]:
16 dp[i] = 0
17 else:
18 dp[i] = min(dp[j] + 1 for j < i if isPal[j+1][i])
19
20 return dp[n-1]