Watch 10 video solutions for Palindrome Partitioning, a medium level problem involving String, Dynamic Programming, Backtracking. This walkthrough by take U forward has 324,255 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, split it into substrings such that every substring is a palindrome. Return all possible palindrome partitionings. Each partition must cover the entire string, and substrings must remain in order.
Approach 1: Recursive Backtracking (O(n^2 * 2^n) time, O(n) space)
This approach explores every possible way to cut the string. Starting at index 0, iterate through all possible end positions and check whether s[start:end] forms a palindrome. If it does, add it to the current path and recursively continue partitioning the remaining suffix. The recursion builds a tree where each branch represents one valid split. Palindrome checking takes O(n), and since the recursion may explore up to 2^n partitions, the total cost becomes O(n^2 * 2^n). This approach is straightforward and demonstrates mastery of backtracking with string validation.
Approach 2: Dynamic Programming + Backtracking (O(n^2 + n * 2^n) time, O(n^2) space)
Repeated palindrome checks slow down the pure backtracking solution. Precompute a DP table dp[i][j] where each entry indicates whether substring s[i:j] is a palindrome. Build this table in O(n^2) using the relation: characters at both ends must match and the inner substring must also be a palindrome. Once the table is ready, run the same backtracking procedure but replace the palindrome check with a constant-time lookup. This reduces redundant work and keeps the recursive exploration focused only on valid splits.
The DP table integrates naturally with the recursion: at each index, iterate through possible end positions and continue only if dp[start][end] is true. This combination of dynamic programming and backtracking avoids repeated substring scans while still generating every valid partition. Memory usage increases to O(n^2) for the table, but runtime becomes significantly faster for longer strings.
Recommended for interviews: The DP + backtracking solution is the expected approach. Interviewers want to see you first model the search space with backtracking, then optimize repeated palindrome checks using string DP preprocessing. Starting with the brute-force recursion shows you understand the structure of the problem; adding the DP table demonstrates optimization and algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(n^2 * 2^n) | O(n) | Best for understanding the recursion tree and brute-force partition generation |
| DP + Backtracking | O(n^2 + n * 2^n) | O(n^2) | Preferred solution when repeated palindrome checks become expensive |