Coding Interview PatternsPalindrome Partitioning
MediumSubsets
Palindrome Partitioning
Explanation & Solution
Description
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.
A palindrome string is a string that reads the same backward as forward.
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Both ["a","a","b"] and ["aa","b"] are valid partitions where every substring is a palindrome.
Constraints
1 <= s.length <= 16scontains only lowercase English letters
Approach
Subsets pattern
1. Define the Palindrome Check
- Create a helper function
isPalindrome(str, left, right)that uses two pointers - Move
leftforward andrightbackward, comparing characters - If all pairs match, the substring is a palindrome
2. Start Backtracking from Index 0
- Call
backtrack(0, [])with an empty current partition - At each call,
startrepresents the beginning of the next unpartitioned portion of the string
3. Try All Possible Substrings from Current Position
- For each position
start, try every possible end index fromstarttos.length - 1 - This generates all substrings starting at the current position
4. Recurse Only on Palindromic Substrings
- Before adding a substring to the current partition, check if it is a palindrome
- If it is, push it to
current, recurse fromend + 1, then pop it (backtrack) - If it is not a palindrome, skip it entirely to prune invalid branches
5. Collect Complete Partitions
- When
start === s.length, we have partitioned the entire string - Push a copy of
currentinto the result array - Sort and return all valid palindrome partitionings
Key Insight
- The key technique is backtracking with pruning: at each position we only explore substrings that are palindromes, avoiding unnecessary work
Time
O(n * 2^n) in the worst case — there are 2^(n-1) ways to partition a string, and checking palindromes takes O(n)Space
O(n) for the recursion stack depth, plus the space needed to store resultsVisualization
Input:
[a, a, b]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps