Palindrome Partitioning
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a classic backtracking algorithm to explore all possible partitions of the string. The core idea is to recursively build a partition. At each step, we try to form the next part of the partition by taking a prefix of the remaining string. If this prefix is a palindrome, we add it to our current partition and recurse on the rest of the string. We backtrack to explore all valid possibilities.
Algorithm
- Define a recursive function
backtrack(start, currentPartition). - The base case is when
startreaches the end of the string. In this case, a valid partition is found, so add a copy ofcurrentPartitionto the results list and return. - In the recursive step, loop with a variable
endfromstartto the end of the string. - For each
end, form a substrings[start...end]. - Check if this substring is a palindrome using a helper function.
- If it is a palindrome, add the substring to
currentPartition. - Make a recursive call:
backtrack(end + 1, currentPartition). - After the recursive call returns, remove the last added substring from
currentPartition. This step is crucial for backtracking, allowing the exploration of other partition possibilities.
Walkthrough
We define a recursive helper function, let's call it backtrack(start, currentPartition).
startkeeps track of the beginning of the substring we are currently trying to partition.currentPartitionis a list that stores the palindromic substrings for the partition being built.
The recursion proceeds as follows:
- Base Case: If
startequals the length of the strings, it means we have successfully found a valid partition for the entire string. We add a copy ofcurrentPartitionto our list of results. - Recursive Step: We iterate from
startto the end of the string. For each indexend, we consider the substring fromstarttoend.- We check if this substring is a palindrome.
- If it is, we add it to
currentPartitionand make a recursive callbacktrack(end + 1, currentPartition)to find partitions for the remaining part of the string. - After the recursive call returns, we must backtrack by removing the last added substring from
currentPartition. This allows us to explore other partition possibilities, for example, by extending the current substring further.
A helper function isPalindrome is used to check if a string is a palindrome, typically by using a two-pointer technique.
class Solution { public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), result); return result; } private void backtrack(String s, int start, List<String> currentPartition, List<List<String>> result) { if (start == s.length()) { result.add(new ArrayList<>(currentPartition)); return; } for (int end = start; end < s.length(); end++) { if (isPalindrome(s, start, end)) { currentPartition.add(s.substring(start, end + 1)); backtrack(s, end + 1, currentPartition, result); currentPartition.remove(currentPartition.size() - 1); } } } private boolean isPalindrome(String s, int low, int high) { while (low < high) { if (s.charAt(low++) != s.charAt(high--)) { return false; } } return true; }}Complexity
Time
O(N * 2^N). The algorithm explores all possible partitions. In the worst case (a string like "aaaa"), there are 2^(N-1) partitions. Generating each partition takes O(N) time. The repeated palindrome checks contribute to a larger constant factor, making it slow in practice, but the overall asymptotic complexity is bounded by O(N * 2^N).
Space
O(N). The maximum depth of the recursion is N. The space for `currentPartition` is also O(N).
Trade-offs
Pros
Conceptually straightforward and easy to implement.
Uses minimal auxiliary space (O(N) for the recursion stack).
Cons
Highly inefficient due to redundant computations. The
isPalindromecheck is called multiple times for the same substrings across different recursive paths, leading to a large number of repeated calculations.
Solutions
Solution
using System.Collections.Generic ; using System.Linq ; public class Solution { public IList < IList < string >> Partition ( string s ) { if ( s . Length == 0 ) return new List < IList < string >>(); var paths = new List < int >[ s . Length ]; for ( var i = 0 ; i < s . Length ; ++ i ) { int j , k ; for ( j = i , k = i + 1 ; j >= 0 && k < s . Length ; -- j , ++ k ) { if ( s [ j ] == s [ k ]) { if ( paths [ k ] == null ) { paths [ k ] = new List < int >(); } paths [ k ]. Add ( j - 1 ); } else { break ; } } for ( j = i , k = i ; j >= 0 && k < s . Length ; -- j , ++ k ) { if ( s [ j ] == s [ k ]) { if ( paths [ k ] == null ) { paths [ k ] = new List < int >(); } paths [ k ]. Add ( j - 1 ); } else { break ; } } } var prevs = new List < int >[ s . Length ]; for ( var i = 0 ; i < s . Length ; ++ i ) { if ( paths [ i ] != null ) { foreach ( var path in paths [ i ]) { if ( path < 0 || prevs [ path ] != null ) { if ( prevs [ i ] == null ) { prevs [ i ] = new List < int >(); } prevs [ i ]. Add ( path ); } } } } var results = new List < IList < string >>(); var temp = new List < string >(); GenerateResults ( prevs , s , s . Length - 1 , temp , results ); return results ; } private void GenerateResults ( List < int >[] prevs , string s , int i , IList < string > temp , IList < IList < string >> results ) { if ( i < 0 ) { results . Add ( temp . Reverse (). ToList ()); } else { foreach ( var prev in prevs [ i ]) { temp . Add ( s . Substring ( prev + 1 , i - prev )); GenerateResults ( prevs , s , prev , temp , results ); temp . RemoveAt ( temp . Count - 1 ); } } } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.