Problem Statement
Given a string s, partition the string so every substring in each partition is a palindrome. Return all possible palindrome partitions.
A palindrome reads the same from left to right and right to left. Each partition must cover the entire string without rearranging characters.
Example 1
Input: s = "aab"
Output: [["a", "a", "b"], ["aa", "b"]]
Explanation: Both partitions cover the full string and every part is a palindrome.
Example 2
Input: s = "a"
Output: [["a"]]
Explanation: A single character is always a palindrome.
Brute Force Approach
This approach tries every possible substring starting from the current index. If the chosen substring is a palindrome, it is added to the current partition and recursion continues for the remaining string. After returning, the substring is removed so other partition choices can be explored. Since palindrome checks are repeated for overlapping substrings, the method performs extra work.
Algorithm
Initialize an empty
answerlist and an emptycurrentpartition to store valid palindrome partitions.Define a helper function to check whether a substring is a palindrome using two pointers moving inward.
Start the recursive function from index
0, whereindexrepresents the first character not yet included in the partition.If
indexreaches the end of the string, add a copy ofcurrenttoanswerand return.Traverse every possible ending index from
indexonward, choose the substring when it is a palindrome, add it tocurrent, and recursively process the remaining string.Remove the chosen substring after recursion returns to restore the previous partition, then return
answerafter all partition choices are explored.
Dry Run
Palindrome Partitioning
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Check if s[left...right] is a palindrome. bool isPalindrome(string& s, int left, int right) { while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } // Generate palindrome partitions from start. void backtrack( int start, string& s, vector<string>& current, vector<vector<string>>& answer ) { // Reached the end, so store the partition. if (start == s.size()) { answer.push_back(current); return; } // Try every possible substring. for (int end = start; end < s.size(); end++) { if (isPalindrome(s, start, end)) { // Choose the palindrome substring. current.push_back(s.substr(start, end - start + 1)); // Explore the remaining string. backtrack(end + 1, s, current, answer); // Undo the choice for the next partition. current.pop_back(); } } }public: // Return all palindrome partitions. vector<vector<string>> partition(string s) { vector<vector<string>> answer; vector<string> current; backtrack(0, s, current, answer); return answer; }};// Driver code.int main() { string s = "aab"; Solution solution; vector<vector<string>> answer = solution.partition(s); for (auto partition : answer) { cout << "["; for (int index = 0; index < partition.size(); index++) { if (index > 0) cout << ", "; cout << partition[index]; } cout << "] "; } return 0;}Complexity Analysis
Time Complexity: O(N2 × 2N), because every cut pattern can be explored and palindrome checks can take O(n) time across many substrings. Here, N is the length of the string s.
Space Complexity: O(N × 2N), because the answer can store exponentially many partitions and each partition can contain up to N strings. Here, N is the length of the string s.
Optimal Approach
This approach first precomputes all palindromic substrings using dynamic programming. During backtracking, palindrome checks become constant-time table lookups instead of repeated scans. The recursion remains the same: choose a palindrome substring, recurse for the remaining string, and backtrack to explore other partitions.
Here, N is the length of the string s. Let dp[i][j] be true when the substring from index i to index j is a palindrome.For a single character, dp[i][i] = true, because one character is always a palindrome.For two or more characters, the first and last characters must match. If the substring length is 2, matching ends are enough. If the substring length is greater than 2, the inner substring must already be a palindrome.
So the recurrence is:
dp[i][j] = (s[i] == s[j]) && (j - i <= 1 || dp[i + 1][j - 1])
The table is filled by increasing substring length, so dp[i + 1][j - 1] is already known before dp[i][j] is computed
Algorithm
Build a DP table
dp[i][j]to store whether the substring from indexitojis a palindrome.Initialize an empty
answerlist and an emptycurrentpartition to store valid palindrome partitions.Start the recursive function from index
0, whereindexrepresents the first character not yet partitioned.If
indexreaches the end of the string, add a copy ofcurrenttoanswerand return.Traverse every ending index from
indexonward and choose the substring only whendp[index][end]istrue; add it tocurrentand recurse fromend + 1.Remove the chosen substring after recursion returns to restore the previous state, then return
answerafter all valid partitions are generated.
Dry Run
palindrome optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Generate partitions using the palindrome table. void backtrack( int start, string& s, vector<vector<int>>& dp, vector<string>& current, vector<vector<string>>& answer ) { // Reached the end, so store the partition. if (start == s.size()) { answer.push_back(current); return; } // Try every possible ending index. for (int end = start; end < s.size(); end++) { if (dp[start][end] == 1) { // Choose the palindrome substring. current.push_back(s.substr(start, end - start + 1)); // Explore the remaining string. backtrack(end + 1, s, dp, current, answer); // Undo the choice for the next partition. current.pop_back(); } } }public: // Return all palindrome partitions using DP. vector<vector<string>> partition(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); // Build palindrome table by substring length. for (int length = 1; length <= n; length++) { for (int start = 0; start + length - 1 < n; start++) { int end = start + length - 1; // Check current ends and inner substring. if (s[start] == s[end] && (length <= 2 || dp[start + 1][end - 1] == 1)) { dp[start][end] = 1; } } } vector<vector<string>> answer; vector<string> current; backtrack(0, s, dp, current, answer); return answer; }};// Driver code.int main() { string s = "aab"; Solution solution; vector<vector<string>> answer = solution.partition(s); for (auto partition : answer) { cout << "["; for (int index = 0; index < partition.size(); index++) { if (index > 0) cout << ", "; cout << partition[index]; } cout << "] "; } return 0;}Complexity Analysis
Time Complexity: O(N2 + N × 2N), because palindrome precomputation takes O(N2) time and copying generated partitions can take O(N × 2N) time.
Space Complexity: O(N2 + N × 2N), because the palindrome table uses O(N2) space and the answer can store exponentially many partitions.
Interview follow-up Questions
Yes. Every single character is a palindrome.
Be the first to add a comment.