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:
Input: s = “aab”
Output:
[["a","a","b"],["aa","b"]]
Example 2:
Input: s = “a”
Output: [["a"]]
Constraints
1 <= s.length <= 16scontains only lowercase English letters.
Approach
- Backtracking – We try to partition the string into all possible substrings.
- t each step, take a prefix
(choice = s[0..i])- If it’s a palindrome, include it in the
current path and recursively partitionthe remaining string. - If not,
skip it.
- If it’s a palindrome, include it in the
- When the remaining string becomes empty, we’ve found a valid partition → add it to the result.
- Use backtracking to
explore allpossibilities (push → recurse → pop). isPalindromeis used to check substrings in O(n) time.
Time Complexity
Time Complexity = O(n * 2n)
Space Complexity
Space Complexity = O(n)
Dry Run
Input:
s = "aab"
State Transitions:
Initialize: result = []
Call backtrack([], "aab")
Level 1:
Loop i = 1 → choice = "a" (palindrome)
path.push("a") → path = ["a"]
Call backtrack(["a"], "ab")
Level 2:
Loop i = 1 → choice = "a" (palindrome)
path.push("a") → path = ["a","a"]
Call backtrack(["a","a"], "b")
Level 3:
Loop i = 1 → choice = "b" (palindrome)
path.push("b") → path = ["a","a","b"]
remainingString empty → result.push(["a","a","b"])
path.pop() → path = ["a","a"]
path.pop() → path = ["a"]
Loop i = 2 → choice = "ab" (not palindrome) → skip
path.pop() → path = []
Loop i = 2 → choice = "aa" (palindrome)
path.push("aa") → path = ["aa"]
Call backtrack(["aa"], "b")
Level 2:
Loop i = 1 → choice = "b" (palindrome)
path.push("b") → path = ["aa","b"]
remainingString empty → result.push(["aa","b"])
path.pop() → path = ["aa"]
path.pop() → path = []
Loop i = 3 → choice = "aab" (not palindrome) → skip
Final Output: [["a","a","b"], ["aa","b"]]
Explanation: The algorithm explores all possible partitions of the string. At each step, it only proceeds if the chosen substring is a palindrome. For "aab", the valid partitions are: - "a" | "a" | "b" - "aa" | "b"
var partition = function(s) {
let result = [];
let isPalindrome = (s) => {
let i =0;
let j = s.length - 1;
while(i < j) {
if(s[i++] != s[j--])
return false;
}
return true;
}
let backtrack = (path, remainingString) => {
if(!remainingString.length) {
result.push([...path]);
}
for(let i=1; i <= remainingString.length; i++){
let choice = remainingString.substring(0, i);
if(!isPalindrome(choice))
continue;
path.push(choice);
backtrack(path, remainingString.substring(i));
path.pop();
}
} backtrack([], s);
return result;
};
class Solution:
def partition(self, s: str):
result = []
def isPalindrome(sub):
return sub == sub[::-1]
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(1, len(remaining) + 1):
choice = remaining[:i]
if not isPalindrome(choice):
continue
path.append(choice)
backtrack(path, remaining[i:])
path.pop()
backtrack([], s)
return result
import java.util.*;
class Solution {
public List> partition(String s) {
List> result = new ArrayList<>();
backtrack(s, new ArrayList<>(), result);
return result;
}
private 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;
}
private void backtrack(String remaining, List path, List> result) {
if (remaining.isEmpty()) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 1; i <= remaining.length(); i++) {
String choice = remaining.substring(0, i);
if (!isPalindrome(choice)) continue;
path.add(choice);
backtrack(remaining.substring(i), path, result);
path.remove(path.size() - 1);
}
}
}
class Solution {
public:
vector> partition(string s) {
vector> result;
vector path;
backtrack(s, path, result);
return result;
}
private:
bool isPalindrome(string &s) {
int i = 0, j = s.size() - 1;
while (i < j) {
if (s[i++] != s[j--]) return false;
}
return true;
}
void backtrack(string remaining, vector &path, vector> &result) {
if (remaining.empty()) {
result.push_back(path);
return;
}
for (int i = 1; i <= remaining.size(); i++) {
string choice = remaining.substr(0, i);
if (!isPalindrome(choice)) continue;
path.push_back(choice);
backtrack(remaining.substr(i), path, result);
path.pop_back();
}
}
};
bool isPalindrome(char *s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) return false;
}
return true;
}
void backtrack(char *s, int start, char path[100][100], int pathLen) {
if (start == strlen(s)) {
printf("[");
for (int i = 0; i < pathLen; i++) {
printf("\"%s\"", path[i]);
if (i < pathLen - 1) printf(", ");
}
printf("]\n");
return;
}
for (int i = start; i < strlen(s); i++) {
if (isPalindrome(s, start, i)) {
strncpy(path[pathLen], s + start, i - start + 1);
path[pathLen][i - start + 1] = '\0';
backtrack(s, i + 1, path, pathLen + 1);
}
}
}
int main() {
char s[] = "aab";
char path[100][100];
backtrack(s, 0, path, 0);
return 0;
}
class Solution {
public IList> Partition(string s) {
var result = new List>();
Backtrack(s, new List(), result);
return result;
}
bool IsPalindrome(string s) {
int i = 0, j = s.Length - 1;
while (i < j) {
if (s[i++] != s[j--]) return false;
}
return true;
}
void Backtrack(string remaining, List path, List> result) {
if (remaining.Length == 0) {
result.Add(new List(path));
return;
}
for (int i = 1; i <= remaining.Length; i++) {
string choice = remaining.Substring(0, i);
if (!IsPalindrome(choice)) continue;
path.Add(choice);
Backtrack(remaining.Substring(i), path, result);
path.RemoveAt(path.Count - 1);
}
}
}
