Problem 599163 · medium · Phase 05 Advanced Algorithms & Graphs

Fewest Cuts Into Palindromes

dynamic programming · palindromes · string partitioning

A ribbon printed with the letters of s is cut into pieces, and every piece must read the same forwards and backwards. Return the fewest cuts needed.

Examples

Input:  s = "abacdc"
Output: 1
Explanation: "aba" | "cdc".

Input:  s = "xyz"
Output: 2

Constraints

  • 1 <= len(s) <= 400
  • s consists of lowercase letters.
  • There are 2**(n-1) ways to place cuts; aim for O(n**2).

Goals

  • Precompute which substrings are palindromes in O(n**2)
  • Combine that table with a prefix DP for the fewest cuts
Starting Python…