119. Palindrome Partitioning II

HardDynamic Programming

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.

Examples

Input: aab

Output: 1

Explanation: Cut into 'aa' | 'b'.

Constraints

  • 1 <= s.length <= 2000
  • s consists of lowercase English letters only.
Loading...

Run checks all cases above. Submit evaluates all test cases.