Palindromic Partitioning

15
0

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 answer list and an empty current partition 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, where index represents the first character not yet included in the partition.

  • If index reaches the end of the string, add a copy of current to answer and return.

  • Traverse every possible ending index from index onward, choose the substring when it is a palindrome, add it to current, and recursively process the remaining string.

  • Remove the chosen substring after recursion returns to restore the previous partition, then return answer after all partition choices are explored.

Dry Run

Palindrome Partitioning

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 index i to j is a palindrome.

  • Initialize an empty answer list and an empty current partition to store valid palindrome partitions.

  • Start the recursive function from index 0, where index represents the first character not yet partitioned.

  • If index reaches the end of the string, add a copy of current to answer and return.

  • Traverse every ending index from index onward and choose the substring only when dp[index][end] is true; add it to current and recurse from end + 1.

  • Remove the chosen substring after recursion returns to restore the previous state, then return answer after all valid partitions are generated.

Dry Run

palindrome optimal

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.

RecursionTCS NQT

Read Similar Blogs

Comments0