# Palindrome Partitioning
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/palindrome-partitioning)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-partitioning
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo)
---
## Problem
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
## Brute-force Backtracking
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Backtracking with Dynamic Programming
This approach enhances the backtracking solution by optimizing the palindrome checking step. Repeatedly checking if a substring is a palindrome is inefficient. We can pre-compute this information for all possible substrings and store it in a 2D boolean array. This technique is a form of dynamic programming. With the pre-computed data, checking if a substring is a palindrome becomes an O(1) lookup inside the backtracking function.
**Time:** O(N * 2^N). The pre-computation takes O(N^2) time. The backtracking part has the same asymptotic complexity as the first approach, O(N * 2^N), which is the dominant term. Although the big-O is the same, this version is much faster in practice because the O(N) palindrome check is replaced by an O(1) table lookup. · **Space:** O(N^2). The DP table requires O(N^2) space, which dominates the O(N) space needed for the recursion stack.
**Pros:** Significantly more time-efficient in practice than the naive backtracking approach.; Eliminates all redundant palindrome computations by pre-calculating them.
**Cons:** Requires extra space for the DP table, leading to O(N^2) space complexity.
### Explanation
The overall structure is still a backtracking algorithm, but we introduce a pre-computation step.

1.  **Pre-computation:** Create a 2D boolean array, `dp[n][n]`, where `n` is the length of the string `s`. `dp[i][j]` will be `true` if the substring `s[i...j]` is a palindrome, and `false` otherwise. We can populate this table in O(N^2) time using the recurrence relation: `dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 2 || dp[i+1][j-1])`. We iterate through all substrings to fill the table.

2.  **Backtracking:** We use the same recursive function `backtrack(start, currentPartition)` as in the previous approach. However, instead of calling a helper function to check for palindromes inside the loop, we simply perform a lookup in our `dp` table: `if (dp[start][end])`. This makes each check an O(1) operation.

This optimization significantly reduces the runtime by eliminating redundant palindrome checks, making it the more efficient solution.

```java
class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1])) {
                    dp[j][i] = true;
                }
            }
        }
        
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result, dp);
        return result;
    }

    private void backtrack(String s, int start, List<String> currentPartition, List<List<String>> result, boolean[][] dp) {
        if (start == s.length()) {
            result.add(new ArrayList<>(currentPartition));
            return;
        }

        for (int end = start; end < s.length(); end++) {
            if (dp[start][end]) {
                currentPartition.add(s.substring(start, end + 1));
                backtrack(s, end + 1, currentPartition, result);
                currentPartition.remove(currentPartition.size() - 1);
            }
        }
    }
}
```
### Algorithm
- First, create a 2D boolean DP table `dp[n][n]`.
- Populate the `dp` table where `dp[i][j]` is true if `s[i...j]` is a palindrome. This can be done in O(N^2) time.
- Then, define the same recursive function `backtrack(start, currentPartition)` as in the brute-force approach.
- The base case and recursive structure remain the same.
- The key difference is inside the loop: instead of calling `isPalindrome(s, start, end)`, we perform an O(1) lookup `if (dp[start][end])`.
- If the lookup is true, add the substring to `currentPartition`, recurse, and then backtrack.

# Solutions
### CSharp

```csharp
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 ); } } } }
```

### Java

```java
import java.util.ArrayList ; import java.util.List ; public class Palindrome_Partitioning { public class Solution_dp { public List < List < String >> partition ( String s ) { int n = s . length (); List < List < String >> res = new ArrayList <>(); List < String > out = new ArrayList <>(); boolean [][] dp = new boolean [ n ][ n ]; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j <= i ; ++ j ) { if ( s . charAt ( i ) == s . charAt ( j ) && ( i - j <= 2 || dp [ j + 1 ][ i - 1 ])) { dp [ j ][ i ] = true ; } } } helper ( s , 0 , dp , out , res ); return res ; } void helper ( String s , int start , boolean [][] dp , List < String > out , List < List < String >> res ) { if ( start == s . length ()) { res . add ( new ArrayList <>( out )); return ; } for ( int i = start ; i < s . length (); ++ i ) { if (! dp [ start ][ i ]) continue ; out . add ( s . substring ( start , i + 1 )); helper ( s , i + 1 , dp , out , res ); out . remove ( out . size () - 1 ); } } } // based on part-I, just count each partition to find min... public class Solution_over_time { List < List < String >> list = new ArrayList <>(); public List < List < String >> partition ( String s ) { if ( s == null || s . length () == 0 ) { return list ; } find ( s , new ArrayList < String >()); return list ; } private void find ( String s , ArrayList < String > currentList ) { if ( s . length () == 0 ) { list . add ( currentList ); return ; } // idea is, scan from index=0, to find each palindrome, then rest substring to next recursion for ( int i = 0 ; i < s . length (); i ++) { String sub = s . substring ( 0 , i + 1 ); // @note: substring 0-s[i] // System.out.println("substring is: " + sub); if ( isPal ( sub )) { ArrayList < String > nextList = new ArrayList <>( currentList ); // deep copy nextList . add ( sub ); find ( s . substring ( i + 1 ), nextList ); } } } private boolean isPal ( String s ) { int i = 0 ; int j = s . length () - 1 ; while ( i <= j ) { // @note: better in if (s.charAt(i++) != s.charAt(j--)) { // @note: 忘了这里的++和--。。。 if ( s . charAt ( i ) != s . charAt ( j )) { return false ; } i ++; j --; } return true ; } } } ############ class Solution { private boolean [][] dp ; private List < List < String >> ans ; private int n ; public List < List < String >> partition ( String s ) { ans = new ArrayList <>(); n = s . length (); dp = new boolean [ n ][ n ]; for ( int i = 0 ; i < n ; ++ i ) { Arrays . fill ( dp [ i ], true ); } for ( int i = n - 1 ; i >= 0 ; -- i ) { for ( int j = i + 1 ; j < n ; ++ j ) { dp [ i ][ j ] = s . charAt ( i ) == s . charAt ( j ) && dp [ i + 1 ][ j - 1 ]; } } dfs ( s , 0 , new ArrayList <>()); return ans ; } private void dfs ( String s , int i , List < String > t ) { if ( i == n ) { ans . add ( new ArrayList <>( t )); return ; } for ( int j = i ; j < n ; ++ j ) { if ( dp [ i ][ j ]) { t . add ( s . substring ( i , j + 1 )); dfs ( s , j + 1 , t ); t . remove ( t . size () - 1 ); } } } }
```

### Python

```python
''' >>> t = [] >>> t.append(1) >>> t.append(2) >>> t.append(3) >>> t [1, 2, 3] >>> t.pop(-1) 3 >>> t [1, 2] >>> t.pop() 2 >>> t [1] >>> t = [1,2,3] >>> t.pop(0) 1 >>> t [2, 3] >>> t = [1,2,3] >>> t.pop(1) 2 >>> t [1, 3] ''' class Solution : def partition ( self , s : str ) -> List [ List [ str ]]: ans = [] n = len ( s ) dp = [[ False ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): for j in range ( i , n ): # <=3 also working, same as <=1 # i==j, or i+1==j dp [ i ][ j ] = s [ i ] == s [ j ] and ( abs ( i - j ) <= 1 or dp [ i + 1 ][ j - 1 ]) def dfs ( s , i , t ): nonlocal n # note: still pass OJ without this nonlocal. default is non-local if i == n : ans . append ( t . copy ()) return for j in range ( i , n ): # including single char dp[i][i] if dp [ i ][ j ]: t . append ( s [ i : j + 1 ]) dfs ( s , j + 1 , t ) t . pop ( - 1 ) dfs ( s , 0 , []) return ans ########### class Solution ( object ): # iteration, real dp def partition ( self , s ): """ :type s: str :rtype: List[List[str]] """ pal = [[ False for i in range ( 0 , len ( s ))] for j in range ( 0 , len ( s ))] ans = [[[]]] + [[] for _ in range ( len ( s ))] # length is n+1 for i in range ( 0 , len ( s )): for j in range ( 0 , i + 1 ): if ( s [ j ] == s [ i ]) and (( j + 1 > i - 1 ) or ( pal [ j + 1 ][ i - 1 ])): pal [ j ][ i ] = True for res in ans [ j ]: a = res + [ s [ j : i + 1 ]] ans [ i + 1 ]. append ( a ) return ans [ - 1 ]
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/palindrome-partitioning/ // Time: O(N * 2^N) // Space: O(N) extra space class Solution { vector < vector < string >> ans ; vector < string > tmp ; bool isPalindrome ( string & s , int i , int j ) { while ( i < j && s [ i ] == s [ j ]) ++ i , -- j ; return i >= j ; } void dfs ( string & s , int start ) { if ( start == s . size ()) { ans . push_back ( tmp ); return ; } for ( int i = start ; i < s . size (); ++ i ) { if ( ! isPalindrome ( s , start , i )) continue ; tmp . push_back ( s . substr ( start , i - start + 1 )); dfs ( s , i + 1 ); tmp . pop_back (); } } public: vector < vector < string >> partition ( string s ) { dfs ( s , 0 ); return ans ; } };
```