The Palindrome Partitioning problem asks you to partition a given string s into all possible lists of substrings such that every substring in each list is a palindrome. A palindrome is a string that reads the same forwards and backwards (e.g., "aba", "aa", "a").
You must return all possible palindrome partitionings of s. Each partitioning should be a list of non-empty substrings, and each substring in the list should be a palindrome.
s can be used only once in each partitioning (no overlaps or reuse).s must be preserved in each partition.
Example:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]
The first step is to recognize that the problem is about exploring all possible ways to break the string into substrings, and for each way, checking if all substrings are palindromes.
A brute-force approach would involve generating every possible way to partition the string, and then checking each substring for the palindrome property. However, this is inefficient because many partitions will contain non-palindromic substrings.
To optimize, we can use backtracking. As we build each partition, we only proceed with substrings that are palindromes. This way, we prune unnecessary branches early and avoid checking invalid partitions.
Think of the problem as exploring a tree: at each character, you can choose to "cut" and start a new substring, but only if the substring formed so far is a palindrome.
s[start:end+1] is a palindrome, we recursively partition the rest of the string from end+1.
s[i:j+1] is a palindrome. However, for most input sizes, the straightforward backtracking is sufficient and easy to implement.
The process continues until all possible partitions have been explored.
Let's walk through the input s = "aab" step by step:
"a" (palindrome). Path = ["a"]. Recurse from index 1."a" (palindrome). Path = ["a", "a"]. Recurse from index 2."b" (palindrome). Path = ["a", "a", "b"]. Recurse from index 3 (end of string). Add ["a", "a", "b"] to result."ab" (not a palindrome). Skip."aa" (palindrome). Path = ["aa"]. Recurse from index 2."b" (palindrome). Path = ["aa", "b"]. Recurse from index 3 (end of string). Add ["aa", "b"] to result."aab" (not a palindrome). Skip.
The final result is [["a","a","b"], ["aa","b"]].
n is 2^{n-1} (since each position between characters can be a cut or not). For each partition, we may need to check each substring for palindrome-ness, which can take O(n) time per substring. So the brute-force time complexity is roughly O(n \cdot 2^n).
O(2^n). Each recursive call adds/removes from the current path, and each valid partition is copied into the result.
O(n) depth, and the result list can store up to O(2^n) partitionings, each containing up to n substrings. So overall space is O(n \cdot 2^n).
The Palindrome Partitioning problem is a classic example of using backtracking to explore all possible solutions efficiently. By only continuing with palindromic substrings, we avoid unnecessary work and prune invalid paths early. The approach is elegant because it leverages recursion, path tracking, and the palindrome property to systematically build all valid partitions. While the worst-case time is exponential, the solution is clean, intuitive, and works well for reasonable input sizes.
class Solution:
def partition(self, s: str):
result = []
path = []
def is_palindrome(sub):
return sub == sub[::-1]
def backtrack(start):
if start == len(s):
result.append(path[:])
return
for end in range(start, len(s)):
if is_palindrome(s[start:end+1]):
path.append(s[start:end+1])
backtrack(end+1)
path.pop()
backtrack(0)
return result
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
function<void(int)> backtrack = [&](int start) {
if (start == s.size()) {
result.push_back(path);
return;
}
for (int end = start; end < s.size(); ++end) {
if (isPalindrome(s, start, end)) {
path.push_back(s.substr(start, end - start + 1));
backtrack(end + 1);
path.pop_back();
}
}
};
backtrack(0);
return result;
}
private:
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) return false;
}
return true;
}
};
import java.util.*;
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
List<String> path = new ArrayList<>();
backtrack(s, 0, path, result);
return result;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
path.add(s.substring(start, end + 1));
backtrack(s, end + 1, path, result);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) return false;
}
return true;
}
}
var partition = function(s) {
const result = [];
const path = [];
function isPalindrome(str, left, right) {
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
function backtrack(start) {
if (start === s.length) {
result.push([...path]);
return;
}
for (let end = start; end < s.length; end++) {
if (isPalindrome(s, start, end)) {
path.push(s.substring(start, end + 1));
backtrack(end + 1);
path.pop();
}
}
}
backtrack(0);
return result;
};