Palindrome Partitioning Minimum Cuts

Find the minimum number of cuts needed to split a string into all palindromes.

dynamic-programming palindrome strings optimization

Write a function `min_cut(s: str) -> int` that takes a string `s` of lowercase English letters and returns the minimum number of cuts needed to partition `s` into substrings such that each substring is a palindrome.

A palindrome reads the same forward and backward. A cut is a position between two characters. The whole string can be considered as one partition (0 cuts) if it is already a palindrome.

Every partition must be contiguous substrings. The function must compute the absolute minimum number of cuts.

- The input string may be empty; an empty string requires 0 cuts.
- The input length can be up to 1500, so an O(n^2) time solution is acceptable and expected.

Implement the exact signature: `def min_cut(s: str) -> int:`.

Constraints

- 0 <= len(s) <= 1500
- s consists of lowercase English letters only.
- Required time complexity: O(n^2), where n = len(s).
- Required space complexity: O(n^2) or O(n).

Example

>>> min_cut('aab')
1
>>> min_cut('abba')
0
>>> min_cut('abc')
2
>>> min_cut('')
0

40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about dynamic programming where dp[i] is the minimum cuts for the prefix s[:i].

Precompute a table is_pal[i][j] that tells if s[i:j+1] is a palindrome.

A palindrome can be built from smaller palindromes: s[i:j+1] is a palindrome if s[i]==s[j] and the inner substring is palindromic.

When iterating over possible last palindrome, use the precomputed table to check palindromes quickly.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.