Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed. This problem is a good base-case DP challenge because the empty-string and single-character states matter a lot.

Input Format

s = lowercase string

Output Format

minimum number of cuts to partition into palindromes

Constraints

  • 1 <= s.length <= 2000; s contains lowercase English letters

Examples

Example 1:

Input:

s = "aab"

Output:

1

Explanation:

Partition as 'aa' | 'b'.

Example 2:

Input:

s = "a"

Output:

0

Explanation:

A single character is already a palindrome.

Loading...
Palindrome Partitioning II - Dp Fundamentals