DiffPush Tier Dynamic Programming · DP on Partition O(n^2) · O(n^2)
A cryptography lab shreds intercepted transmissions into chunks so that every chunk reads the same forwards and backwards — only then can each fragment be archived in the symmetric vault. Each slice of the tape costs one cut, and the archivist wants as few cuts as possible while keeping every fragment palindromic.
Input: A string s.
Output: Return the minimum number of cuts so that every resulting substring is a palindrome.
1 <= len(s) <= 2000s consists of lowercase English lettersInput: {"s":"aab"}
Output: 1
One cut yields "aa" + "b" — both palindromes.
Input: {"s":"a"}
Output: 0
A single character is already palindromic; no cut needed.