Palindrome Partitioning II

Palindrome Partitioning II is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Palindrome Partitioning subpattern.

Problem statement

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.

Topics and companies

Topics: Dynamic Programming.

Reported in interviews at Amazon, Google.

How to practise Palindrome Partitioning II on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Palindrome Partitioning II in the code editor, or read the Palindrome Partitioning II editorial for a worked solution with its approach and complexity analysis.

Where Palindrome Partitioning II sits in the DSA pattern sheet

• Backtracking Patterns pattern guide
• Palindrome Partitioning subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Palindrome Partitioning II

Other problems that use the same Palindrome Partitioning and Backtracking Patterns techniques:

• Palindrome Partitioning — Medium, same subpattern
• Pseudo-Palindromic Paths in a Binary Tree — Medium, same subpattern
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combinations — Medium, same pattern
• Combination Sum — Medium, same pattern
• Combination Sum II — Medium, same pattern