Scale Engineer

Palindrome Partitioning

Med
#0131Time: 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).4 companies
Patterns
Dynamic ProgrammingBacktracking
Data structures
String
Companies
InfosysUberWalmart LabsYahoo

Prompt

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 <= 16
  • s contains 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 start reaches the end of the string. In this case, a valid partition is found, so add a copy of currentPartition to the results list and return.
  • In the recursive step, loop with a variable end from start to the end of the string.
  • For each end, form a substring s[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).

  • start keeps track of the beginning of the substring we are currently trying to partition.
  • currentPartition is a list that stores the palindromic substrings for the partition being built.

The recursion proceeds as follows:

  • Base Case: If start equals the length of the string s, it means we have successfully found a valid partition for the entire string. We add a copy of currentPartition to our list of results.
  • Recursive Step: We iterate from start to the end of the string. For each index end, we consider the substring from start to end.
    • We check if this substring is a palindrome.
    • If it is, we add it to currentPartition and make a recursive call backtrack(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 isPalindrome check is called multiple times for the same substrings across different recursive paths, leading to a large number of repeated calculations.

Solutions

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.

← Previous

Previous problem

Next →

Next problem