131. Palindrome Partitioning
Palindrome Partitioning (LeetCode 131) is a Medium 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
Palindrome Partitioning 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 backtracking to explore all possible partitions of the string and build solutions incrementally.
- At each step, try to partition the string by checking substrings starting from the current index and recurse on the remaining substring.
- Before recursing, verify if the current substring is a palindrome to ensure the partition meets the problem's criteria.
The reference solution runs in O(N * 2^N) time and O(N * 2^N) space.
The Palindrome Partitioning 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 all possible palindrome partitioning of s.
Example 1:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a" Output: [["a"]]
Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters.
Topics and companies
Topics: String, Dynamic Programming, Backtracking.
Reported in interviews at Amazon, Apple, Google.
How to practise Palindrome Partitioning on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. 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 * 2^N) time and O(N * 2^N) space.
Open Palindrome Partitioning in the code editor, or read the Palindrome Partitioning editorial for a worked solution with its approach and complexity analysis.
Where Palindrome Partitioning sits in the DSA pattern sheet
Problems related to Palindrome Partitioning
Other problems that use the same Palindrome Partitioning and Backtracking Patterns techniques:
- Palindrome Partitioning II — Hard, 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 FAQ
What is the LeetCode number of Palindrome Partitioning?
Palindrome Partitioning is LeetCode problem 131, rated Medium.
What pattern is used to solve Palindrome Partitioning?
Palindrome Partitioning 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?
The reference solution runs in O(N * 2^N) time and O(N * 2^N) space.
Which companies ask Palindrome Partitioning?
Palindrome Partitioning has been reported in interviews at Amazon, Apple, Google.