Log inSign up
mediumLeetCodeNot Started

Palindrome Partitioning

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

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 · Standard 'aab':

Input: s = "aab"
Output: [["a", "a", "b"], ["aa", "b"]]
Explanation: Both [a, a, b] and [aa, b] consist solely of palindromes.

Example 2 · Single Character 'a':

Input: s = "a"
Output: [["a"]]
Explanation: Single character is trivially a palindrome.

Constraints:

  • 1 <= s.length <= 16
  • s contains only lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the string partitioning backtracking template.
  • Understand the synergy between Dynamic Programming (precomputation) and Backtracking (generation).
  • Analyze the 2^(N-1) partition space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partition a string into contiguous palindromic substrings
  • Return all possible combinations of partitions
  • Short string length (N <= 16)

Algorithmic Decision Tree:

  • Precompute a 2D boolean table isPalindrome[i][j] using DP.
  • In backtrack(start): loop end from start to n - 1.
  • If isPalindrome[start][end]: push s.substring(start, end + 1), recurse backtrack(end + 1), and pop.

Connected Patterns:

Palindrome Partitioning IIRestore IP AddressesWord Break II

1. Generate All Partitions + Post-Validation

Intuition

A string of length N has N - 1 potential cut positions. Generate all 2^(N-1) cut subsets. For each partition, verify whether every segment is a palindrome. If all are valid, add partition to result.

When to apply: Baseline comparison to understand total partition space.

Algorithm

  1. Iterate mask from 0 to (1 << (n - 1)) - 1 to define cuts.
  2. Split string according to mask cuts.
  3. Verify each substring using two-pointer palindrome check.
  4. If all valid, add to result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 bool isPalindrome(const string& s) {
9 int l = 0, r = s.length() - 1;
10 while (l < r) {
11 if (s[l++] != s[r--]) return false;
12 }
13 return true;
14 }
15
16public:
17 vector<vector<string>> partition(string s) {
18 int n = s.length();
19 vector<vector<string>> result;
20
21 for (int mask = 0; mask < (1 << (n - 1)); mask++) {
22 vector<string> current;
23 int start = 0;
24 bool valid = true;
25
26 for (int i = 0; i < n - 1; i++) {
27 if (mask & (1 << i)) {
28 string sub = s.substr(start, i - start + 1);
29 if (!isPalindrome(sub)) { valid = false; break; }
30 current.push_back(sub);
31 start = i + 1;
32 }
33 }
34 if (valid) {
35 string sub = s.substr(start);
36 if (isPalindrome(sub)) {
37 current.push_back(sub);
38 result.push_back(current);
39 }
40 }
41 }
42 return result;
43 }
44};
45
46int main() {
47 Solution sol;
48 auto res = sol.partition("aab");
49 for (const auto& p : res) {
50 cout << "[ ";
51 for (const string& s : p) cout << s << " ";
52 cout << "] ";
53 }
54 cout << endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(2^N * N^2) — Generates 2^(N-1) partitions, each validated in O(N2) time.
  • Space complexity: O(N) — Stores temporary partition segments.

2. Standard Backtracking with Two-Pointer Palindrome Check

Intuition

Iterate end from start to n - 1. If isPalindrome(s, start, end) is true, push substring, recurse on end + 1, and pop.

When to apply: Standard intuitive implementation without 2D DP precomputation.

Algorithm

  1. In backtrack(start, current):
  2. - If start == n, add copy of current to result.
  3. - For end from start to n - 1:
  4. - If isPalindrome(s, start, end):
  5. - Push s[start..end].
  6. - Recurse backtrack(end + 1, current).
  7. - Pop substring.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 bool isPalindrome(const string& s, int l, int r) {
9 while (l < r) {
10 if (s[l++] != s[r--]) return false;
11 }
12 return true;
13 }
14
15 void backtrack(int start, const string& s, vector<string>& current, vector<vector<string>>& result) {
16 if (start == s.length()) {
17 result.push_back(current);
18 return;
19 }
20
21 for (int end = start; end < s.length(); end++) {
22 if (isPalindrome(s, start, end)) {
23 current.push_back(s.substr(start, end - start + 1));
24 backtrack(end + 1, s, current, result);
25 current.pop_back(); // backtrack
26 }
27 }
28 }
29
30public:
31 vector<vector<string>> partition(string s) {
32 vector<vector<string>> result;
33 vector<string> current;
34 backtrack(0, s, current, result);
35 return result;
36 }
37};
38
39int main() {
40 Solution sol;
41 auto res = sol.partition("aab");
42 for (const auto& p : res) {
43 cout << "[ ";
44 for (const string& s : p) cout << s << " ";
45 cout << "] ";
46 }
47 cout << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(2^N * N) — Generates all valid palindrome partitions directly.
  • Space complexity: O(N) — Recursion depth is N.

3. Backtracking with DP Palindrome Precomputation (Optimal)

Intuition

Precompute dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]). Then run backtracking: when considering s[start..end], check dp[start][end] in O(1) time.

When to apply: The optimal standard for palindrome partitioning.

Algorithm

  1. Initialize dp[n][n] boolean table.
  2. Fill dp diagonally or bottom-up for all substrings s[i..j].
  3. Run backtrack(start):
  4. - If start == n: add current to result.
  5. - For end from start to n - 1:
  6. - If dp[start][end]:
  7. - Push s.substring(start, end + 1).
  8. - Recurse backtrack(end + 1).
  9. - Pop substring.

Palindrome Partition Cut Tree Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Start at start = 0
Visual state
Values and pointers at this exact step
tree
Root
s: 'aab', start: 0

Node order shown; add connections to display explicit tree edges.

Variables at this step
start
0
validPrefixes
["a","aa"]
Why this step matters

Start at start = 0. DP precomputation shows a (0..0) and aa (0..1) are palindromes.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 void backtrack(int start, const string& s, const vector<vector<bool>>& dp,
9 vector<string>& current, vector<vector<string>>& result) {
10 int n = s.length();
11 if (start == n) {
12 result.push_back(current);
13 return;
14 }
15
16 for (int end = start; end < n; end++) {
17 if (dp[start][end]) {
18 current.push_back(s.substr(start, end - start + 1));
19 backtrack(end + 1, s, dp, current, result);
20 current.pop_back(); // backtrack
21 }
22 }
23 }
24
25public:
26 vector<vector<string>> partition(string s) {
27 int n = s.length();
28 vector<vector<bool>> dp(n, vector<bool>(n, false));
29
30 // DP Palindrome Precomputation
31 for (int len = 1; len <= n; len++) {
32 for (int i = 0; i <= n - len; i++) {
33 int j = i + len - 1;
34 if (s[i] == s[j]) {
35 dp[i][j] = (len <= 2) || dp[i + 1][j - 1];
36 }
37 }
38 }
39
40 vector<vector<string>> result;
41 vector<string> current;
42 backtrack(0, s, dp, current, result);
43 return result;
44 }
45};
46
47int main() {
48 Solution sol;
49 auto res = sol.partition("aab");
50 for (const auto& p : res) {
51 cout << "[ ";
52 for (const string& s : p) cout << s << " ";
53 cout << "] ";
54 }
55 cout << endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(2^N * N) — Precomputing DP takes O(N2). Backtracking generates all partitions with O(1) validation per cut.
  • Space complexity: O(N^2) — DP table takes O(N2) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Generate All Partitions + ValidatorO(2^N * N^2)O(N)Generate all 2^(N-1) cut subsets and validate post-facto.Post-validation of invalid partitions
2.Backtracking with Two-Pointer Palindrome CheckO(2^N * N)O(N)Two-pointer check on the fly during recursive traversal.Repeated palindrome scans
3.Backtracking with DP PrecomputationOptimalO(2^N * N)O(N^2)Precompute 2D table dp[i][j] for O(1) palindrome queries.Partition string copy cost

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using end + 1 as the starting index of the next recursive call vs start + 1 (must advance to end + 1 to skip the consumed substring).

Pitfall 2:

Not cloning the current path array before pushing to result.

Crucial Edge Cases to Validate:

  • Single Character: a -> [[a]].
  • All Identical Characters: aaa -> [[a, a, a], [a, aa], [aa, a], [aaa]].
  • No Multi-char Palindromes: abc -> [[a, b, c]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the O(N2) DP palindrome precomputation upfront to showcase both DP and Backtracking skills.
  2. Draw the cut decision tree on aab for visual clarity.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How many total ways can a string of length N be partitioned into contiguous non-empty substrings?

2.What is the DP transition to check if substring s[i..j] is a palindrome?

Back to DSA Sheet