Given a string, split it into palindromic substrings using the fewest possible cuts.
Palindrome Partitioning II
You are given a string s. Your task is to divide s into one or more contiguous substrings such that every substring is a palindrome.
Return the minimum number of cuts needed so that every part of the partition is palindromic.
A cut is made between two adjacent characters. If the whole string is already a palindrome, the answer is 0.
Goal
Find the smallest number of cuts required to partition the entire string into palindromic pieces.
Input Format
- A single string
s. - The string contains lowercase English letters in the typical formulation of this problem.
Output Format
- Return one integer: the minimum number of cuts needed to partition
sinto palindromic substrings.
Constraints
1 <= s.length <= 2000is a common interview-scale constraint for this problem.- Time complexity better than brute force partitioning is expected.
- Palindromic substrings must be contiguous.
Example 1
Input
s = "aab"
Output
1
Explanation
One optimal partition is "aa" | "b", which uses 1 cut.
Example 2
Input
s = "a"
Output
0
Explanation
A single character is already a palindrome, so no cuts are needed.
Show 1 more example
Example 3
Input
s = "abccbc"
Output
2
Explanation
One optimal partition is "a" | "bccb" | "c", which uses 2 cuts.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.