palindrome-partitioning-ii

< Previous 　　　　　　　　　　　　　　　　 Next >

132. Palindrome Partitioning II (Hard)

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: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lower-case English letters only.

Related Topics

[String] [Dynamic Programming]

Similar Questions

1. Palindrome Partitioning (Medium)
2. Palindrome Partitioning IV (Hard)