Palindrome Partitioning
Last Updated: March 29, 2026
Understanding the Problem
We need to find every way to split a string into parts where each part reads the same forwards and backwards. This is not about finding the fewest cuts or the longest palindrome. We need all valid partitionings.
Think of it like placing dividers in the string. For "aab", we could place dividers as "a|a|b" or "aa|b". Each placement that results in all palindromic pieces is a valid answer.
The key observation is that this is a decision problem at each position. Starting from the left, we try every possible palindromic prefix, and then recursively partition the remainder. If we can reach the end of the string with every piece being a palindrome, we have found a valid partitioning.
Key Constraints:
1 <= s.length <= 16→ With n at most 16, exponential approaches like backtracking are perfectly fine. In the worst case (all same characters), the number of valid partitions can be 2^(n-1), which for n=16 is 32,768. Very manageable.scontains only lowercase English letters → No special characters to worry about. Palindrome checks are straightforward character comparisons.
Approach 1: Backtracking with Inline Palindrome Checks
Intuition
The most natural way to approach this problem is to build partitions left to right. Starting from index 0, we try every possible first piece: "a", "aa", "aab". If a piece is a palindrome, we recurse on whatever is left. If we reach the end of the string, every piece we collected along the way is palindromic, so we have found a valid partition.
This is classic backtracking. At each position, we explore multiple choices (where to end the current piece), and we backtrack when we need to try a different choice.
For the palindrome check itself, the simplest approach is to just compare characters from both ends of the substring and work inward. This takes O(n) time per check, but with n at most 16, it is fast enough.
Algorithm
- Start a recursive function with the current index in the string and the current list of palindromic pieces collected so far.
- If the current index equals the length of the string, we have partitioned the entire string. Add a copy of the current list to the results.
- Otherwise, try every possible end index from the current index to the end of the string.
- For each end index, check if the substring from the current index to the end index is a palindrome.
- If it is, add it to the current list, recurse with the next index being end + 1, then remove the substring (backtrack).
Example Walkthrough
Code
- Time Complexity: O(n * 2^n). In the worst case (all characters the same), every partition is valid, giving us 2^(n-1) partitions. For each partition, we spend O(n) time checking palindromes and copying strings.
- Space Complexity: O(n). The recursion stack goes at most n levels deep. The current partition path has at most n strings. Output space is not counted as auxiliary.
The repeated work here is in the palindrome checks. Every time we consider substring s[i..j], we re-check it character by character, even if we checked the same substring in a different branch. What if we precomputed all palindrome information upfront so every check became O(1)?
Approach 2: Backtracking with DP-Precomputed Palindrome Table
Intuition
The backtracking logic from Approach 1 is already the right framework. We cannot avoid exploring all valid partitions. But we can eliminate redundant palindrome checks by precomputing a 2D table.
Here is the key insight for the precomputation: a substring s[i..j] is a palindrome if and only if s[i] == s[j] AND s[i+1..j-1] is also a palindrome (or the inner part has length 0 or 1, making it trivially a palindrome). This gives us a clean dynamic programming recurrence.
We fill a boolean table isPalin[i][j] bottom-up. Single characters are always palindromes. Two consecutive characters are palindromes if they match. For longer substrings, we check the two endpoints and look up the inner substring in our table.
Once this table is built, every palindrome check during backtracking becomes a simple O(1) table lookup instead of an O(n) character scan.
The palindrome table captures a simple recursive truth: a string is a palindrome if its first and last characters match and the string between them is also a palindrome. By filling this table bottom-up (starting from the shortest substrings), we ensure that when we compute isPalin[i][j], the answer for isPalin[i+1][j-1] is already available. During backtracking, instead of scanning characters each time, we simply look up isPalin[start][end]. The backtracking tree is exactly the same as Approach 1, but each node does less work.
Algorithm
- Build a 2D boolean table
isPalinof size n x n, whereisPalin[i][j]is true if s[i..j] is a palindrome. - Fill the table: iterate over all possible substring lengths from 1 to n. For each length, check all starting positions.
- Run the same backtracking as Approach 1, but replace the isPalindrome function call with a table lookup
isPalin[start][end].
Example Walkthrough
Code
- Time Complexity: O(n^2 + n * 2^n). The precomputation fills an n x n table in O(n^2). The backtracking still explores up to 2^(n-1) partitions, spending O(n) time per partition to copy strings.
- Space Complexity: O(n^2). The palindrome table takes O(n^2) space. The recursion stack is O(n). Output space is not counted as auxiliary.
The palindrome table makes each check O(1), but different backtracking branches can still reach the same index and re-explore identical suffixes. What if we cached the results for each suffix so it is computed only once?
Approach 3: DP with Memoization (Cached Suffix Partitions)
Intuition
Notice something about the backtracking tree: when we reach index i, the set of all valid partitions of s[i..n-1] is the same regardless of how we got to index i. In Approach 2, we recompute this every time. But we could store it.
The idea is to define dp[i] as the list of all valid palindrome partitions of the suffix starting at index i. To compute dp[i], we try every index j from i to n-1 where s[i..j] is a palindrome. For each such j, we prepend s[i..j] to every partition in dp[j+1]. The base case is dp[n] = [[]] (an empty partition for the empty suffix).
This transforms the problem from backtracking into a bottom-up DP where we build from the end of the string backward.
Each suffix s[i..n-1] has a fixed set of valid palindrome partitions, regardless of what came before index i. By computing these bottom-up and storing them, we assemble the final answer by combining palindromic prefixes with already-computed suffix partitions. This is the classic DP pattern of breaking a problem into non-overlapping subproblems along a single dimension.
Algorithm
- Precompute the isPalin table as in Approach 2.
- Create a memoization array where dp[i] stores all valid partitions of the suffix s[i..n-1].
- Build from right to left: for each start index i, try all palindromic prefixes s[i..j] and combine them with dp[j+1].
- The base case is dp[n] = [[]] (empty partition for empty suffix).
- Return dp[0].
Example Walkthrough
Code
- Time Complexity: O(n^2 + n * 2^n). The palindrome table is O(n^2). The DP builds all partitions. In the worst case, there are O(2^n) total partitions, and each has average length O(n) to construct and store.
- Space Complexity: O(n * 2^n). We store all partitions for every suffix. In the worst case (e.g., "aaa...a"), the total number of stored partition strings is exponential.