Statement

Suppose you are given a string, s. You need to perform the minimum number of cuts to divide the string into substrings, such that all the resulting substrings are palindromes.

Let’s say you have the following string:

  • “apple”

The resulting substrings after performing the minimum number of cuts are:

  • “a”|“pp”|“l”|“e”

So, a minimum of 33 cuts are required.

Constraints:

  • 11 \leq s.length 1.5×103\leq 1.5\times10^3
  • s consists of only lowercase English characters.

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.