Find all Palindromic Partitions of a String
Last Updated : 18 Jun, 2025
Given a string s, find all possible ways to partition it such that every substring in the partition is a palindrome.
Examples:
Input: s = "geeks"
Output: [[g, e, e, k, s], [g, ee, k, s]]
Explanation: [g, e, e, k, s] and [g, ee, k, s] are the only partitions of "geeks" where each substring is a palindrome.
Input: s = "abcba"
Output: [[a, b, c, b, a], [a, bcb, a], [abcba]]
Explanation: [a, b, c, b, a], [a, bcb, a] and [abcba] are the only partitions of "abcba" where each substring is a palindrome.
[Approach 1] Using Recursion and Backtracking
The main idea is to use backtracking to explore all combinations of substrings starting from each index, including a substring in the current partition only if it is a palindrome.
Step-By-Step Approach:
- Start at index 0 of the string.
- Generate all substrings starting from the current index.
- Check if the current substring is a palindrome.
- If it is, add it to the current partition path.
- Recursively continue from the next index.
- If the end of the string is reached, add the current path to the result.
- Backtrack by removing the last added substring and try the next possibility.
C++ #include <iostream> #include <vector> #include <string> #include <algorithm> #include <numeric> using namespace std; // Check if the given string is a palindrome bool isPalindrome(string& s) { int i = 0, j = s.size() - 1; while (i < j) { if (s[i++] != s[j--]) return false; } return true; } // Recursive function to find all palindromic partitions void backtrack(int idx, string& s, vector<string>& curr, vector<vector<string>>& res) { if (idx == s.size()) { // Store valid partition res.push_back(curr); return; } string temp = ""; for (int i = idx; i < s.size(); ++i) { temp += s[i]; if (isPalindrome(temp)) { // Choose the substring curr.push_back(temp); // Explore further backtrack(i + 1, s, curr, res); // Backtrack curr.pop_back(); } } } // Return all palindromic partitions of string s vector<vector<string>> palinParts(string& s) { vector<vector<string>> res; vector<string> curr; backtrack(0, s, curr, res); return res; } int main() { string s = "geeks"; vector<vector<string>> res = palinParts(s); // Print result: one partition per line for (int i = 0; i < res.size(); ++i) { for (int j = 0; j < res[i].size(); ++j) { cout << res[i][j]; if (j != res[i].size() - 1) cout << " "; } cout << "\n"; } return 0; } import java.util.*; class GfG { // Check if a string is a palindrome public boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (s.charAt(i++) != s.charAt(j--)) return false; } return true; } // Recursive helper to find all palindromic partitions public void backtrack(int idx, String s, List<String> curr, List<ArrayList<String>> res) { if (idx == s.length()) { // Reached end, store current partition res.add(new ArrayList<>(curr)); return; } StringBuilder temp = new StringBuilder(); for (int i = idx; i < s.length(); i++) { temp.append(s.charAt(i)); String sub = temp.toString(); if (isPalindrome(sub)) { // Choose the substring curr.add(sub); // Explore further backtrack(i + 1, s, curr, res); // Backtrack curr.remove(curr.size() - 1); } } } // Returns all palindromic partitions public ArrayList<ArrayList<String>> palinParts(String s) { ArrayList<ArrayList<String>> res = new ArrayList<>(); backtrack(0, s, new ArrayList<>(), res); return res; } public static void main(String[] args) { GfG ob = new GfG(); String s = "geeks"; ArrayList<ArrayList<String>> res = ob.palinParts(s); // Print each partition for (ArrayList<String> part : res) { System.out.println(String.join(" ", part)); } } } # Check if the string is a palindrome def isPalindrome(s): return s == s[::-1] # Backtracking function to generate all palindromic partitions def backtrack(idx, s, curr, res): if idx == len(s): # Save the current valid partition res.append(curr[:]) return temp = "" for i in range(idx, len(s)): temp += s[i] if isPalindrome(temp): # Choose substring curr.append(temp) # Explore further backtrack(i + 1, s, curr, res) # Backtrack curr.pop() # Generate all palindromic partitions and sort them def palinParts(s): res = [] backtrack(0, s, [], res) return res if __name__ == "__main__": s = "geeks" res = palinParts(s) for part in res: print(" ".join(part)) using System; using System.Collections.Generic; using System.Linq; class GfG { // Check if a string is a palindrome public bool isPalindrome(string s) { int i = 0, j = s.Length - 1; while (i < j) { if (s[i++] != s[j--]) return false; } return true; } // Backtracking function to find all palindromic partitions public void backtrack(int idx, string s, List<string> curr, List<List<string>> res) { if (idx == s.Length) { // Valid partition found res.Add(new List<string>(curr)); return; } string temp = ""; for (int i = idx; i < s.Length; i++) { temp += s[i]; if (isPalindrome(temp)) { // Choose the substring curr.Add(temp); // Explore further backtrack(i + 1, s, curr, res); // Backtrack curr.RemoveAt(curr.Count - 1); } } } // Generate all palindromic partitions public List<List<string>> palinParts(string s) { List<List<string>> res = new List<List<string>>(); backtrack(0, s, new List<string>(), res); return res; } public static void Main() { GfG ob = new GfG(); string s = "geeks"; var res = ob.palinParts(s); // Print each partition line by line foreach (var part in res) { Console.WriteLine(string.Join(" ", part)); } } } // Check if a string is a palindrome function isPalindrome(s) { return s === s.split('').reverse().join(''); } // Backtracking function to find all palindromic partitions function backtrack(idx, s, curr, res) { if (idx === s.length) { // Valid partition found res.push([...curr]); return; } let temp = ""; for (let i = idx; i < s.length; i++) { temp += s[i]; if (isPalindrome(temp)) { // Choose the substring curr.push(temp); // Explore further backtrack(i + 1, s, curr, res); // Backtrack curr.pop(); } } } function palinParts(s) { const res = []; backtrack(0, s, [], res); return res; } // Driver code let s = "geeks"; let res = palinParts(s); res.forEach(part => console.log(part.join(" "))); Time Complexity: O(n² × 2n), for exploring all possible partitions (2n) and checking each substring for palindrome in O(n) time.
Auxiliary Space: O(n × 2n), for storing all palindromic partitions and using recursion stack up to depth n.
[Approach 2] Using Bit Manipulation
The main idea is systematically explores all ways to cut a string into parts and checks which ones consist only of palindromic substrings. It uses binary representation to model cut/no-cut choices between characters
- If there n characters in the string, then there are n-1 positions to put a space or say cut the string.
- Each of these positions can be given a binary number 1 (If a cut is made in this position) or 0 (If no cut is made in this position).
- This will give a total of 2n-1 partitions and for each partition check whether this partition is palindrome or not.
Illustration:
Input : geeks
0100 → ["ge","eks"] (not valid)
1011 → ["g","ee","k","s"] (valid)
1111 → ["g","e","e","k","s"] (valid)
0000 → ["geeks"] (not valid)
C++ #include <iostream> #include <vector> #include <string> using namespace std; vector<vector<string>> ans; // Check if all substrings in the partition are palindromes bool isAllPalindromes(vector<string> &partition) { for (auto &str : partition) { int i = 0, j = str.size() - 1; while (i < j) { if (str[i] != str[j]) return false; i++; j--; } } return true; } // Generate partition of string based on the binary cut pattern void createPartition(string &s, string &cutPattern) { vector<string> currentPartition; string subStr; // Start the first substring with the first character subStr.push_back(s[0]); for (int i = 0; i < cutPattern.size(); i++) { // If no cut, append next character to current substring if (cutPattern[i] == '0') { subStr.push_back(s[i + 1]); } // If cut, push current substring and start a new one else { currentPartition.push_back(subStr); subStr.clear(); subStr.push_back(s[i + 1]); } } // Push the last substring currentPartition.push_back(subStr); // Store partition if all substrings are palindromes if (isAllPalindromes(currentPartition)) { ans.push_back(currentPartition); } } // Recursively generate all cut patterns (bit strings) void generateCut(string &s, string &cutPattern) { // When pattern is complete, create partition if (cutPattern.size() == s.size() - 1) { createPartition(s, cutPattern); return; } // Try with a cut cutPattern.push_back('1'); generateCut(s, cutPattern); cutPattern.pop_back(); // Try without a cut cutPattern.push_back('0'); generateCut(s, cutPattern); cutPattern.pop_back(); } // Generate all palindromic partitions of the string vector<vector<string>> palinParts(string &s) { string cutPattern; generateCut(s, cutPattern); return ans; } int main() { string s = "geeks"; vector<vector<string>> result = palinParts(s); for (auto &partition : result) { for (auto &segment : partition) { cout << segment << " "; } cout << "\n"; } return 0; } import java.util.ArrayList; class GfG{ static ArrayList<ArrayList<String>> ans = new ArrayList<>(); // Check if all substrings in the partition are palindromes static boolean isAllPalindromes(ArrayList<String> partition) { for (String str : partition) { int i = 0, j = str.length() - 1; while (i < j) { if (str.charAt(i) != str.charAt(j)) return false; i++; j--; } } return true; } // Generate partition of string based on the binary cut pattern static void createPartition(String s, String cutPattern) { ArrayList<String> currentPartition = new ArrayList<>(); StringBuilder subStr = new StringBuilder(); // Start the first substring with the first character subStr.append(s.charAt(0)); for (int i = 0; i < cutPattern.length(); i++) { // If no cut, append next character to current substring if (cutPattern.charAt(i) == '0') { subStr.append(s.charAt(i + 1)); } // If cut, push current substring and start a new one else { currentPartition.add(subStr.toString()); subStr = new StringBuilder(); subStr.append(s.charAt(i + 1)); } } // Push the last substring currentPartition.add(subStr.toString()); // Store partition if all substrings are palindromes if (isAllPalindromes(currentPartition)) { ans.add(currentPartition); } } // Recursively generate all cut patterns (bit strings) static void generateCut(String s, String cutPattern) { // When pattern is complete, create partition if (cutPattern.length() == s.length() - 1) { createPartition(s, cutPattern); return; } // Try with a cut generateCut(s, cutPattern + '1'); // Try without a cut generateCut(s, cutPattern + '0'); } // Generate all palindromic partitions of the string static ArrayList<ArrayList<String>> palinParts(String s) { generateCut(s, ""); return ans; } public static void main(String[] args) { String s = "geeks"; ArrayList<ArrayList<String>> result = palinParts(s); for (ArrayList<String> partition : result) { for (String segment : partition) { System.out.print(segment + " "); } System.out.println(); } } } # Stores all valid palindromic partitions ans = [] # Check if all substrings in the partition are palindromes def isAllPalindromes(partition): for s in partition: i, j = 0, len(s) - 1 while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return True # Generate partition of string based on the binary cut pattern def createPartition(s, cutPattern): currentPartition = [] subStr = s[0] for i in range(len(cutPattern)): # If no cut, append next character to current substring if cutPattern[i] == '0': subStr += s[i + 1] # If cut, push current substring and start a new one else: currentPartition.append(subStr) subStr = s[i + 1] # Push the last substring currentPartition.append(subStr) # Store partition if all substrings are palindromes if isAllPalindromes(currentPartition): ans.append(currentPartition) # Recursively generate all cut patterns (bit strings) def generateCut(s, cutPattern): # When pattern is complete, create partition if len(cutPattern) == len(s) - 1: createPartition(s, cutPattern) return # Try with a cut generateCut(s, cutPattern + '1') # Try without a cut generateCut(s, cutPattern + '0') # Generate all palindromic partitions of the string def palinParts(s): generateCut(s, "") return ans if __name__ == "__main__": s = "geeks" result = palinParts(s) for partition in result: print(" ".join(partition)) using System; using System.Collections.Generic; using System.Text; class GfG{ static List<List<string>> ans = new List<List<string>>(); // Check if all substrings in the partition are palindromes static bool isAllPalindromes(List<string> partition){ foreach (string str in partition){ int i = 0, j = str.Length - 1; while (i < j){ if (str[i] != str[j]) return false; i++; j--; } } return true; } // Generate partition of string based on the binary cut pattern static void createPartition(string s, string cutPattern){ List<string> currentPartition = new List<string>(); StringBuilder subStr = new StringBuilder(); // Start the first substring with the first character subStr.Append(s[0]); for (int i = 0; i < cutPattern.Length; i++){ // If no cut, append next character to current substring if (cutPattern[i] == '0'){ subStr.Append(s[i + 1]); } // If cut, push current substring and start a new one else{ currentPartition.Add(subStr.ToString()); subStr.Clear(); subStr.Append(s[i + 1]); } } // Push the last substring currentPartition.Add(subStr.ToString()); // Store partition if all substrings are palindromes if (isAllPalindromes(currentPartition)) { ans.Add(currentPartition); } } // Recursively generate all cut patterns (bit strings) static void generateCut(string s, string cutPattern) { // When pattern is complete, create partition if (cutPattern.Length == s.Length - 1) { createPartition(s, cutPattern); return; } // Try with a cut generateCut(s, cutPattern + '1'); // Try without a cut generateCut(s, cutPattern + '0'); } // Generate all palindromic partitions of the string static List<List<string>> palinParts(string s){ generateCut(s, ""); return ans; } static void Main() { string s = "geeks"; List<List<string>> result = palinParts(s); foreach (var partition in result) { foreach (var segment in partition) { Console.Write(segment + " "); } Console.WriteLine(); } } } // Stores all valid palindromic partitions let ans = []; // Check if all substrings in the partition are palindromes function isAllPalindromes(partition) { for (let str of partition) { let i = 0, j = str.length - 1; while (i < j) { if (str[i] !== str[j]) { return false; } i++; j--; } } return true; } // Generate partition of string based on the binary cut pattern function createPartition(s, cutPattern) { let currentPartition = []; let subStr = s[0]; for (let i = 0; i < cutPattern.length; i++) { // If no cut, append next character to current substring if (cutPattern[i] === '0') { subStr += s[i + 1]; } // If cut, push current substring and start a new one else { currentPartition.push(subStr); subStr = s[i + 1]; } } // Push the last substring currentPartition.push(subStr); // Store partition if all substrings are palindromes if (isAllPalindromes(currentPartition)) { ans.push(currentPartition); } } // Recursively generate all cut patterns (bit strings) function generateCut(s, cutPattern) { // When pattern is complete, create partition if (cutPattern.length === s.length - 1) { createPartition(s, cutPattern); return; } // Try with a cut generateCut(s, cutPattern + '1'); // Try without a cut generateCut(s, cutPattern + '0'); } // Generate all palindromic partitions of the string function palinParts(s) { generateCut(s, ""); return ans; } // Driver Code const s = "geeks"; const result = palinParts(s); for (const partition of result) { console.log(partition.join(" ")); } Time Complexity: O(n² × 2n) for generating all possible partitions (2n) and checking each partition for palindromes (up to O(n2) per partition).
Auxiliary Space: O(n × 2n), to store all palindromic partitions, each potentially having up to n substrings.
[Expected Approach] Backtracking with Memoization
The Idea is uses dynamic programming to precompute all substrings of the input string that are palindromes in O(n²) time. This precomputation helps in quickly checking whether a substring is a palindrome during the recursive backtracking phase. Then, it uses backtracking to explore all possible partitions of the string and collects only those partitions where every substring is a palindrome.
C++ #include <iostream> #include <vector> #include <string> using namespace std; // Precompute all palindromic substrings in s void palindromes(const string& s, vector<vector<bool>> &dp) { int n = s.size(); // All single characters are palindromes for (int i = 0; i < n; ++i) dp[i][i] = true; // Check two-character substrings for (int i = 0; i < n - 1; ++i) dp[i][i + 1] = (s[i] == s[i + 1]); // Check substrings of length 3 or more using bottom-up DP for (int len = 3; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]; } } } // Recursive function to find all palindromic partitions void backtrack(int idx, const string& s, vector<string>& curr, vector<vector<string>>& res, vector<vector<bool>> &dp) { // If we have reached the end of the string, store current partition if (idx == s.size()) { res.push_back(curr); return; } // Try all substrings starting from index idx for (int i = idx; i < s.size(); ++i) { // If s[idx..i] is a palindrome, we can include it if (dp[idx][i]) { // Choose the substring curr.push_back(s.substr(idx, i - idx + 1)); // Explore further from next index backtrack(i + 1, s, curr, res, dp); // Undo the choice (backtrack) curr.pop_back(); } } } // Return all palindromic partitions of string s vector<vector<string>> palinParts(string& s) { // DP table to store if substring s[i..j] is a palindrome vector<vector<bool>> dp(s.size()+1, vector<bool> (s.size()+1, false)); // Precompute all palindromic substrings using DP palindromes(s, dp); // Final result vector<vector<string>> res; // Current partition vector<string> curr; // Begin backtracking from index 0 backtrack(0, s, curr, res, dp); return res; } int main() { string s = "geeks"; // Get all palindromic partitions vector<vector<string>> res = palinParts(s); // Print each valid partition for (auto& partition : res) { for (auto& part : partition) { cout << part << " "; } cout << "\n"; } return 0; } import java.util.ArrayList; class GfG { // Precompute all palindromic substrings in s public static void palindromes(String s, boolean[][] dp) { int n = s.length(); // All single characters are palindromes for (int i = 0; i < n; ++i) dp[i][i] = true; // Check two-character substrings for (int i = 0; i < n - 1; ++i) dp[i][i + 1] = (s.charAt(i) == s.charAt(i + 1)); // Check substrings of length 3 or more using bottom-up DP for (int len = 3; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1]; } } } // Recursive function to find all palindromic partitions public static void backtrack(int idx, String s, ArrayList<String> curr, ArrayList<ArrayList<String>> res, boolean[][] dp) { // If we have reached the end of the string, store current partition if (idx == s.length()) { res.add(new ArrayList<>(curr)); return; } // Try all substrings starting from index idx for (int i = idx; i < s.length(); ++i) { // If s[idx..i] is a palindrome, we can include it if (dp[idx][i]) { // Choose the substring curr.add(s.substring(idx, i + 1)); // Explore further from next index backtrack(i + 1, s, curr, res, dp); // Undo the choice (backtrack) curr.remove(curr.size() - 1); } } } // Return all palindromic partitions of string s public static ArrayList<ArrayList<String>> palinParts(String s) { // DP table to store if substring s[i..j] is a palindrome boolean[][] dp = new boolean[s.length()][s.length()]; // Precompute all palindromic substrings using DP palindromes(s, dp); // Final result ArrayList<ArrayList<String>> res = new ArrayList<>(); // Current partition ArrayList<String> curr = new ArrayList<>(); // Begin backtracking from index 0 backtrack(0, s, curr, res, dp); return res; } public static void main(String[] args) { String s = "geeks"; // Get all palindromic partitions ArrayList<ArrayList<String>> res = palinParts(s); // Print each valid partition for (ArrayList<String> partition : res) { for (String part : partition) { System.out.print(part + " "); } System.out.println(); } } } # Precompute all palindromic substrings in s def palindromes(s, dp): n = len(s) # All single characters are palindromes for i in range(n): dp[i][i] = True # Check two-character substrings for i in range(n - 1): dp[i][i + 1] = (s[i] == s[i + 1]) # Check substrings of length 3 or more using bottom-up DP for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1] # Recursive function to find all palindromic partitions def backtrack(idx, s, curr, res, dp): # If we have reached the end of the string, store current partition if idx == len(s): res.append(list(curr)) return # Try all substrings starting from index idx for i in range(idx, len(s)): # If s[idx..i] is a palindrome, we can include it if dp[idx][i]: # Choose the substring curr.append(s[idx:i + 1]) # Explore further from next index backtrack(i + 1, s, curr, res, dp) # Undo the choice (backtrack) curr.pop() # Return all palindromic partitions of string s def palinParts(s): n = len(s) # DP table to store if substring s[i..j] is a palindrome dp = [[False] * n for _ in range(n)] # Precompute all palindromic substrings using DP palindromes(s, dp) # Final result res = [] # Current partition curr = [] # Begin backtracking from index 0 backtrack(0, s, curr, res, dp) return res if __name__ == "__main__": s = "geeks" # Get all palindromic partitions result = palinParts(s) # Print each valid partition for partition in result: print(" ".join(partition)) using System; using System.Collections.Generic; class GfG{ // Precompute all palindromic substrings in s static void palindromes(string s, bool[,] dp){ int n = s.Length; // All single characters are palindromes for (int i = 0; i < n; ++i) dp[i, i] = true; // Check two-character substrings for (int i = 0; i < n - 1; ++i) dp[i, i + 1] = (s[i] == s[i + 1]); // Check substrings of length 3 or more using bottom-up DP for (int len = 3; len <= n; ++len){ for (int i = 0; i <= n - len; ++i){ int j = i + len - 1; dp[i, j] = (s[i] == s[j]) && dp[i + 1, j - 1]; } } } // Recursive function to find all palindromic partitions static void backtrack(int idx, string s, List<string> curr, List<List<string>> res, bool[,] dp){ // If we have reached the end of the string, store current partition if (idx == s.Length){ res.Add(new List<string>(curr)); return; } // Try all substrings starting from index idx for (int i = idx; i < s.Length; ++i){ // I s[idx..i] is a palindrome, we can include it if (dp[idx, i]){ // Choose the substring curr.Add(s.Substring(idx, i - idx + 1)); // Explore further from next index backtrack(i + 1, s, curr, res, dp); // Undo the choice (backtrack) curr.RemoveAt(curr.Count - 1); } } } // Return all palindromic partitions of string s static List<List<string>> palinParts(string s){ // DP table to store if substring s[i..j] is a palindrome bool[,] dp = new bool[s.Length, s.Length]; // Precompute all palindromic substrings using DP palindromes(s, dp); // Final result List<List<string>> res = new List<List<string>>(); // Current partition List<string> curr = new List<string>(); // Begin backtracking from index 0 backtrack(0, s, curr, res, dp); return res; } static void Main(){ string s = "geeks"; // Get all palindromic partitions var res = palinParts(s); // Print each valid partition foreach (var partition in res){ foreach (var part in partition){ Console.Write(part + " "); } Console.WriteLine(); } } } // Precompute all palindromic substrings in s function palindromes(s, dp) { const n = s.length; // All single characters are palindromes for (let i = 0; i < n; i++) dp[i][i] = true; // Check two-character substrings for (let i = 0; i < n - 1; i++) dp[i][i + 1] = (s[i] === s[i + 1]); // Check substrings of length 3 or more using bottom-up DP for (let len = 3; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; dp[i][j] = (s[i] === s[j]) && dp[i + 1][j - 1]; } } } // Recursive function to find all palindromic partitions function backtrack(idx, s, curr, res, dp) { // If we have reached the end of the string, store current partition if (idx === s.length) { res.push([...curr]); return; } // Try all substrings starting from index idx for (let i = idx; i < s.length; i++) { // If s[idx..i] is a palindrome, we can include it if (dp[idx][i]) { // Choose the substring curr.push(s.substring(idx, i + 1)); // Explore further from next index backtrack(i + 1, s, curr, res, dp); // Undo the choice (backtrack) curr.pop(); } } } // Return all palindromic partitions of string s function palinParts(s) { const n = s.length; const dp = Array.from({ length: n }, () => Array(n).fill(false)); // Precompute all palindromic substrings using DP palindromes(s, dp); // Final result const res = []; // Current partition const curr = []; // Begin backtracking from index 0 backtrack(0, s, curr, res, dp); return res; } // Example usage const s = "geeks"; // Get all palindromic partitions const result = palinParts(s); // Print each valid partition for (const partition of result) { console.log(partition.join(" ")); } Time Complexity: O(n² + 2n×n), (n2) time for precomputing palindromic substrings and O(2n × n) for backtracking through all partitions.
Auxiliary Space: O(n2), for the DP table and O(n) for the recursion stack and temporary storage during backtracking.
A similar optimization can be applied to the bitmask-based approach by precomputing all palindromic substrings in O(n²) using dynamic programming. This reduces the palindrome-checking time per partition from O(n) to O(1), thereby improving the overall time complexity from O(n2 × 2n) to O(n × 2n).
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile