132. Palindrome Partitioning II
Palindrome Partitioning II (LeetCode 132) 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.
How to solve Palindrome Partitioning II
Palindrome Partitioning II is a Palindrome Partitioning problem, part of Backtracking Patterns. Partition string into palindromic substrings using backtracking.
Work towards the solution in these steps:
- Consider using dynamic programming or backtracking to explore different ways to partition the string.
- How can you efficiently check whether a substring is a palindrome to avoid repeated computations?
- Try precomputing a 2D table that indicates if s[i..j] is a palindrome to speed up your partitioning logic.
The reference solution runs in O(n) time and O(1) space.
The Palindrome Partitioning II solution and editorial walks through the full approach with reference code.
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
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
Palindrome Partitioning II FAQ
What is the LeetCode number of Palindrome Partitioning II?
Palindrome Partitioning II is LeetCode problem 132, rated Hard.
What pattern is used to solve Palindrome Partitioning II?
Palindrome Partitioning II is a Palindrome Partitioning problem. It belongs to the Backtracking Patterns pattern, in the Palindrome Partitioning subpattern.
What is the time complexity of Palindrome Partitioning II?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Palindrome Partitioning II?
Palindrome Partitioning II has been reported in interviews at Amazon, Google.