2026-01-08 22:11:32 +0300 MSK

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        cuts = [i for i in range(n)] 

        for center in range(n):
            for left, right in ((center, center), (center, center + 1)):
                while left >= 0 and right < n and s[left] == s[right]:
                    if left == 0:
                        cuts[right] = 0 
                    else:
                        cuts[right] = min(cuts[right], cuts[left - 1] + 1)
                    left -= 1
                    right += 1

        return cuts[-1]