Loading problem…
Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.
Example 1
Input: s = aab
Output: 1
Explanation: One cut gives "aa" | "b", and both pieces are palindromes. "aab" itself is not a palindrome, so at least one cut is needed.
Example 2
Input: s = a
Output: 0
Explanation: "a" is already a palindrome, so no cuts are needed.
Example 3
Input: s = ab
Output: 1
Explanation: "ab" is not a palindrome, so it needs one cut: "a" | "b".
Precompute which substrings are palindromes, then let dp[i] be the fewest cuts for the prefix ending at i: 0 if the whole prefix is a palindrome, else 1 + the best earlier cut before a palindromic tail.
Run checks all cases above. Submit evaluates all test cases.