Watch 10 video solutions for Palindrome Partitioning, a medium level problem involving String, Dynamic Programming, Backtracking. This walkthrough by take U forward has 420,666 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 16s contains only lowercase English letters.Problem Overview: Given a string s, return all possible ways to partition it so every substring in the partition is a palindrome. Each partition must cover the entire string, and the result includes every valid combination.
Approach 1: Recursive Backtracking (O(n * 2^n) time, O(n) space)
The straightforward approach uses backtracking to try every possible cut in the string. Start from index 0, expand the substring one character at a time, and check whether the current segment is a palindrome using two pointers from both ends. If it is, add it to the current path and recursively process the remaining suffix. When the recursion reaches the end of the string, the current path represents a valid partition. This approach explores all partition possibilities, which leads to roughly 2^n combinations in the worst case. Each palindrome check costs O(n), so the total runtime becomes O(n * 2^n). Space complexity is O(n) for the recursion stack and current partition path, excluding output.
Approach 2: Dynamic Programming + Backtracking (O(n * 2^n) time, O(n^2) space)
The bottleneck in the previous method is repeatedly checking whether substrings are palindromes. You can eliminate that repeated work by precomputing palindrome information using dynamic programming. Build a 2D table dp[i][j] where each cell indicates whether the substring s[i..j] is a palindrome. Fill this table by expanding substring lengths: single characters are palindromes, and longer substrings are palindromes if their endpoints match and the inner substring is also a palindrome. This preprocessing costs O(n^2) time and space.
Once the DP table is built, run the same backtracking process. Instead of scanning characters each time, check dp[start][end] in O(1). This avoids repeated substring comparisons and makes the search significantly faster in practice. The recursion still explores up to 2^n partitions, so the overall time complexity remains O(n * 2^n), but with much smaller constant factors.
Recommended for interviews: Interviewers typically expect the backtracking solution first since it naturally models the partition decision process. Demonstrating the DP optimization shows stronger algorithmic thinking because you identify and remove redundant palindrome checks. Starting with brute-force backtracking proves you understand the search space; adding the DP table shows you can optimize repeated work in string problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(n * 2^n) | O(n) | Good starting solution in interviews. Simple to implement and demonstrates understanding of partition search. |
| Dynamic Programming + Backtracking | O(n * 2^n) | O(n^2) | Preferred approach when palindrome checks repeat often. DP table enables O(1) substring validation. |