Palindrome Partitioning solution and explanation
Infosys
Google
9 more videos on this problem
L17. Palindrome Partitioning | Leetcode | Recursion | C++ | Javatake U forward · 24:34 · 442K views
Palindrome Partitioning - Backtracking - Leetcode 131NeetCode · 10:24 · 214K views
Generate All Palindromic Decompositions Of A String ("Palindrome Partitioning" on Leetcode)Back To Back SWE · 11:56 · 53K views
Palindrome Partitioning | Backtracking | The Proven Template | Leetcode 131 | codestorywithMIKcodestorywithMIK · 25:25 · 39K views
Palindrome Partitioning | Live Coding with Explanation | Leetcode #131Algorithms Made Easy · 6:44 · 7K views
LeetCode 131. Palindrome Partitioning Explanation and Solutionhappygirlzt · 11:30 · 4K views
[Java] Leetcode 131. Palindrome Partitioning [Backtracking #7]Eric Programming · 11:14 · 3K views
LEETCODE 131 (JAVASCRIPT) | PALINDROME PARTITIONING IAndy Gala · 12:33 · 2K views
Palindrome Partitioning | Leetcode 131| Live coding session 🔥🔥🔥 | BacktrackingCoding Decoded · 2:42 · 871 views
LeetCode 131. Palindrome PartitioningHappy Coding · 15:22 · 685 views
The problem
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 <= 16scontains only lowercase English letters.
Approach overview
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 1: Recursive Backtracking
Recursive Backtracking: This approach involves using recursion to explore all possible ways to partition the string. At each position, we check all possible substrings starting from that position, and if a substring is palindrome, we recursively partition the remaining substring. This way, we build possible partitions incrementally.
def is_palindrome(s):
return s == s[::-1]
def backtrack(start, path, res, s):
if start == len(s):
res.append(path[:])
return
for end in range(start + 1, len(s) + 1):
if is_palindrome(s[start:end]):
path.append(s[start:end])
backtrack(end, path, res, s)
path.pop()
def partition(s):
res = []
backtrack(0, [], res, s)
return res
# Example Usage
# print(partition('aab'))import java.util.*;
public class Solution {
private boolean isPalindrome(String s, int low, int high) {
while (low < high) {
if (s.charAt(low++) != s.charAt(high--)) {
return false;
}
}
return true;
}
private void backtrack(int start, List<String> path, List<List<String>> res, String s) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int end = start + 1; end <= s.length(); end++) {
if (isPalindrome(s, start, end - 1)) {
path.add(s.substring(start, end));
backtrack(end, path, res, s);
path.remove(path.size() - 1);
}
}
}
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
backtrack(0, new ArrayList<>(), res, s);
return res;
}
// Example Usage
// public static void main(String[] args) {
// Solution sol = new Solution();
// System.out.println(sol.partition("aab"));
// }
}This Python solution uses a helper function backtrack to perform recursive backtracking. We check each substring from the current position start. If it is a palindrome, we include it in our current path (path) and recursively continue partitioning the remainder of the string. If start reaches the end of the string, we add the current path to the results (res).
Time Complexity: O(2n * n), since we can have 2^n possible partitions and checking each partition takes O(n).
Space Complexity: O(n), where n is the depth of the recursive call stack.
Approach 2: Dynamic Programming with Backtracking
Dynamic Programming with Backtracking: This approach utilizes dynamic programming to precompute whether substrings are palindromes, reducing the on-the-fly palindrome check complexity in backtracking.
def partition(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
# Fill the DP table
for i in range(n):
dp[i][i] = True # Single letter is a palindrome
for length in range(2, n + 1):
for start in range(n - length + 1):
end = start + length - 1
if length == 2:
dp[start][end] = s[start] == s[end]
else:
dp[start][end] = (s[start] == s[end]) and dp[start + 1][end - 1]
def backtrack(start, path):
if start == n:
res.append(path[:])
return
for end in range(start, n):
if dp[start][end]:
path.append(s[start:end+1])
backtrack(end + 1, path)
path.pop()
res = []
backtrack(0, [])
return res
# Example Usage
# print(partition('aab'))#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.length();
vector<vector<bool>> dp(n, vector<bool>(n, false));
vector<vector<string>> res;
// Fill the DP table
for (int i = 0; i < n; ++i) dp[i][i] = true; // Single character palindrome
for (int length = 2; length <= n; ++length) {
for (int start = 0; start <= n - length; ++start) {
int end = start + length - 1;
if (length == 2)
dp[start][end] = (s[start] == s[end]);
else
dp[start][end] = (s[start] == s[end]) && dp[start + 1][end - 1];
}
}
vector<string> path;
backtrack(0, path, res, dp, s);
return res;
}
private:
void backtrack(int start, vector<string>& path, vector<vector<string>>& res, vector<vector<bool>>& dp, string& s) {
if (start == s.length()) {
res.push_back(path);
return;
}
for (int end = start; end < s.length(); ++end) {
if (dp[start][end]) {
path.push_back(s.substr(start, end - start + 1));
backtrack(end + 1, path, res, dp, s);
path.pop_back();
}
}
}
// Example Usage
// int main() {
// Solution sol;
// auto result = sol.partition("aab");
// for (const auto& partition : result) {
// for (const auto& part : partition) {
// cout << part << " ";
// }
// cout << endl;
// }
// }
};This Python solution first uses dynamic programming to fill a table dp where dp[i][j] is True if the substring s[i:j+1] is a palindrome. Then, using backtracking, it generates partitions. If a substring s[start:end+1] is a palindrome (checked in O(1) time using dp), it adds it to the current path and continues recursively until the entire string is partitioned.
Time Complexity: O(n2 + 2n * n). Filling the dp table takes O(n2), and backtracking takes O(2n * n).
Space Complexity: O(n2), required for the dp table.
Approach 3: Preprocessing + DFS (Backtracking)
We can use dynamic programming to preprocess whether any substring in the string is a palindrome, i.e., f[i][j] indicates whether the substring s[i..j] is a palindrome.
Next, we design a function dfs(i), which represents starting from the i-th character of the string and partitioning it into several palindromic substrings, with the current partition scheme being t.
If i = |s|, it means the partitioning is complete, and we add t to the answer array and then return.
Otherwise, we can start from i and enumerate the end position j from small to large. If s[i..j] is a palindrome, we add s[i..j] to t, then continue to recursively call dfs(j+1). When backtracking, we need to pop s[i..j].
The time complexity is O(n times 2^n), and the space complexity is O(n^2). Here, n is the length of the string.
function partition(s: string): string[][] {
const n = s.length;
const f: boolean[][] = Array.from({ length: n }, () => Array(n).fill(true));
for (let i = n - 1; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
}
}
const ans: string[][] = [];
const t: string[] = [];
const dfs = (i: number) => {
if (i === n) {
ans.push(t.slice());
return;
}
for (let j = i; j < n; ++j) {
if (f[i][j]) {
t.push(s.slice(i, j + 1));
dfs(j + 1);
t.pop();
}
}
};
dfs(0);
return ans;
}public class Solution {
private int n;
private string s;
private bool[,] f;
private IList<IList<string>> ans = new List<IList<string>>();
private IList<string> t = new List<string>();
public IList<IList<string>> Partition(string s) {
n = s.Length;
this.s = s;
f = new bool[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
f[i, j] = true;
}
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i, j] = s[i] == s[j] && f[i + 1, j - 1];
}
}
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == n) {
ans.Add(new List<string>(t));
return;
}
for (int j = i; j < n; ++j) {
if (f[i, j]) {
t.Add(s.Substring(i, j + 1 - i));
dfs(j + 1);
t.RemoveAt(t.Count - 1);
}
}
}
}func partition(s string) (ans [][]string) {
n := len(s)
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
for j := range f[i] {
f[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = s[i] == s[j] && f[i+1][j-1]
}
}
t := []string{}
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, append([]string(nil), t...))
return
}
for j := i; j < n; j++ {
if f[i][j] {
t = append(t, s[i:j+1])
dfs(j + 1)
t = t[:len(t)-1]
}
}
}
dfs(0)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Backtracking | Time Complexity: O(2n * n), since we can have 2^n possible partitions and checking each partition takes O(n). |
| Dynamic Programming with Backtracking | Time Complexity: O(n2 + 2n * n). Filling the |
| Preprocessing + DFS (Backtracking) | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Palindrome Partitioning easy or hard?
Palindrome Partitioning is generally classified as a medium-level problem. The basic backtracking idea is straightforward, but handling recursion correctly and optimizing palindrome checks with dynamic programming makes it a solid interview challenge.
Palindrome Partitioning Python/Java solution
Python and Java implementations typically use recursive backtracking to explore partitions. Each recursive call expands the substring boundary and verifies whether the segment is a palindrome. Optimized versions add a DP table to cache palindrome results so each substring check runs in O(1).
How to solve Palindrome Partitioning in O(n)?
Generating all palindrome partitions cannot be solved in O(n) because the output itself can contain up to 2^n combinations. The best achievable approach is O(n * 2^n) using backtracking with a dynamic programming table that precomputes palindrome substrings in O(n^2).
What is the best approach for Palindrome Partitioning?
Backtracking combined with dynamic programming for palindrome checks is the most efficient practical approach. Precompute a DP table where dp[i][j] indicates whether substring s[i..j] is a palindrome, then run recursive backtracking to build partitions. This avoids repeated substring scans and reduces constant overhead while exploring the partition space.
Is Palindrome Partitioning asked at Google/Amazon/Meta?
Palindrome Partitioning is a common interview problem at large tech companies including Amazon, Google, and Meta. It tests backtracking, recursion design, and optimization with dynamic programming, making it a frequent medium-level string problem in technical interviews.
What data structure is used in Palindrome Partitioning?
The solution primarily uses recursion with a dynamic list to store the current partition path. Many optimized implementations also use a 2D boolean DP table to store palindrome results for substrings, enabling constant-time checks during backtracking.
What is the time complexity of Palindrome Partitioning?
The overall time complexity is O(n * 2^n). A string of length n can produce up to 2^n possible partitions in the worst case, and each partition construction may involve up to O(n) work. With DP precomputation, palindrome validation becomes O(1), but the exponential number of partitions remains the dominant factor.