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.


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


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