Palindrome Partitioning

This question is asked by Google. Given a string s, return all possible partitions of s such that each substring is a palindrome.

Example(s)

Example 1:

Input: s = "abcba"
Output: [
    ["a","b","c","b","a"],
    ["a","bcb","a"],
    ["abcba"]
]
Explanation:
Partition 1: "a" + "b" + "c" + "b" + "a" (all single characters are palindromes)
Partition 2: "a" + "bcb" + "a" ("bcb" is a palindrome)
Partition 3: "abcba" (entire string is a palindrome)

Example 2:

Input: s = "aab"
Output: [
    ["a","a","b"],
    ["aa","b"]
]
Explanation:
Partition 1: "a" + "a" + "b"
Partition 2: "aa" + "b" ("aa" is a palindrome)

Example 3:

Input: s = "a"
Output: [["a"]]
Explanation:
Only one character, so only one partition.

Example 4:

Input: s = "racecar"
Output: [
    ["r","a","c","e","c","a","r"],
    ["r","a","cec","a","r"],
    ["r","aceca","r"],
    ["racecar"]
]
Explanation:
Multiple palindromic substrings create various partitions.

Solution

The solution uses Backtracking (DFS):

1. Backtracking: Explore all possible partitions
2. Palindrome check: For each substring, check if it's a palindrome
3. Recursive partitioning: If substring is palindrome, recursively partition the rest
4. Base case: When we reach the end, add current partition to results

JavaScript Solution

JavaScript Solution - Backtracking

/**
* Find all palindrome partitions
* @param {string} s - Input string
* @return {string[][]} - All possible palindrome partitions
*/
function partition(s) {
const result = [];
const current = [];

/**
 * Check if a substring is a palindrome
 */
function isPalindrome(str, left, right) {
  while (left < right) {
    if (str[left] !== str[right]) {
      return false;
    }
    left++;
    right--;
  }
  return true;
}

/**
 * Backtracking function
 */
function backtrack(start) {
  // Base case: reached end of string
  if (start === s.length) {
    result.push([...current]);
    return;
  }
  
  // Try all possible substrings starting from 'start'
  for (let end = start; end < s.length; end++) {
    // Check if substring s[start...end] is a palindrome
    if (isPalindrome(s, start, end)) {
      // Add palindrome substring to current partition
      current.push(s.substring(start, end + 1));
      
      // Recursively partition the remaining string
      backtrack(end + 1);
      
      // Backtrack: remove last added substring
      current.pop();
    }
  }
}

backtrack(0);
return result;
}

// Test cases
console.log('Example 1:', partition("abcba")); 
// [["a","b","c","b","a"], ["a","bcb","a"], ["abcba"]]

console.log('Example 2:', partition("aab")); 
// [["a","a","b"], ["aa","b"]]

console.log('Example 3:', partition("a")); 
// [["a"]]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Backtracking

from typing import List

def partition(s: str) -> List[List[str]]:
  """
  Find all palindrome partitions
  
  Args:
      s: Input string
      
  Returns:
      List[List[str]]: All possible palindrome partitions
  """
  result = []
  current = []
  
  def is_palindrome(left: int, right: int) -> bool:
      """Check if substring s[left:right+1] is a palindrome"""
      while left < right:
          if s[left] != s[right]:
              return False
          left += 1
          right -= 1
      return True
  
  def backtrack(start: int):
      """Backtracking function"""
      # Base case: reached end of string
      if start == len(s):
          result.append(current[:])
          return
      
      # Try all possible substrings starting from 'start'
      for end in range(start, len(s)):
          # Check if substring s[start:end+1] is a palindrome
          if is_palindrome(start, end):
              # Add palindrome substring to current partition
              current.append(s[start:end + 1])
              
              # Recursively partition the remaining string
              backtrack(end + 1)
              
              # Backtrack: remove last added substring
              current.pop()
  
  backtrack(0)
  return result

# Test cases
print('Example 1:', partition("abcba"))  
# [['a', 'b', 'c', 'b', 'a'], ['a', 'bcb', 'a'], ['abcba']]

print('Example 2:', partition("aab"))  
# [['a', 'a', 'b'], ['aa', 'b']]

print('Example 3:', partition("a"))  
# [['a']]

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (With DP for Palindrome Check)

Here's an optimized version using DP to precompute palindromes:

JavaScript DP Optimized

/**
 * Optimized: Use DP to precompute palindromes
 */
function partitionOptimized(s) {
  const n = s.length;
  const result = [];
  const current = [];
  
  // dp[i][j] = whether s[i...j] is a palindrome
  const dp = Array(n).fill().map(() => Array(n).fill(false));
  
  // Precompute palindromes
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (i === j) {
        dp[i][j] = true; // Single character
      } else if (i + 1 === j) {
        dp[i][j] = s[i] === s[j]; // Two characters
      } else {
        dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
      }
    }
  }
  
  function backtrack(start) {
    if (start === n) {
      result.push([...current]);
      return;
    }
    
    for (let end = start; end < n; end++) {
      if (dp[start][end]) {
        current.push(s.substring(start, end + 1));
        backtrack(end + 1);
        current.pop();
      }
    }
  }
  
  backtrack(0);
  return result;
}

Python DP Optimized

def partition_optimized(s: str) -> List[List[str]]:
    """
    Optimized: Use DP to precompute palindromes
    """
    n = len(s)
    result = []
    current = []
    
    # dp[i][j] = whether s[i:j+1] is a palindrome
    dp = [[False] * n for _ in range(n)]
    
    # Precompute palindromes
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if i == j:
                dp[i][j] = True  # Single character
            elif i + 1 == j:
                dp[i][j] = s[i] == s[j]  # Two characters
            else:
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
    
    def backtrack(start: int):
        if start == n:
            result.append(current[:])
            return
        
        for end in range(start, n):
            if dp[start][end]:
                current.append(s[start:end + 1])
                backtrack(end + 1)
                current.pop()
    
    backtrack(0)
    return result

Complexity

• Time Complexity: O(N × 2^N) - Where N is the length of the string. In the worst case, there are 2^N possible partitions, and checking each palindrome takes O(N) time. With DP optimization: O(N × 2^N) but with faster palindrome checks.
• Space Complexity: O(N) - For the recursion stack and current partition (excluding output space).

Approach

The solution uses Backtracking (DFS):

1. Backtracking function:

   • Start from position start in the string
   • Try all possible substrings starting from start

2. Palindrome check:

   • For each substring s[start...end], check if it's a palindrome
   • Can use two-pointer approach or DP precomputation

3. Recursive partitioning:

   • If substring is palindrome, add it to current partition
   • Recursively partition the remaining string s[end+1...]
   • Backtrack by removing the last added substring

4. Base case:

   • When start === s.length, we've partitioned the entire string
   • Add current partition to results

Key Insights

• Backtracking: Explore all possible partitions
• Palindrome check: Verify each substring is a palindrome
• Recursive structure: Partition remaining string after each palindrome
• O(2^N) partitions: In worst case (all characters same)
• DP optimization: Precompute palindromes for faster checks

Step-by-Step Example

Let's trace through Example 1: s = "abcba"

s = "abcba"
result = []
current = []

backtrack(0):
  start = 0
  Try end = 0: s[0:1] = "a" → palindrome ✓
    current = ["a"]
    backtrack(1):
      start = 1
      Try end = 1: s[1:2] = "b" → palindrome ✓
        current = ["a", "b"]
        backtrack(2):
          start = 2
          Try end = 2: s[2:3] = "c" → palindrome ✓
            current = ["a", "b", "c"]
            backtrack(3):
              start = 3
              Try end = 3: s[3:4] = "b" → palindrome ✓
                current = ["a", "b", "c", "b"]
                backtrack(4):
                  start = 4
                  Try end = 4: s[4:5] = "a" → palindrome ✓
                    current = ["a", "b", "c", "b", "a"]
                    backtrack(5):
                      start = 5 === length → add to result
                      result = [["a","b","c","b","a"]]
                    current.pop() → ["a","b","c","b"]
                current.pop() → ["a","b","c"]
              Try end = 4: s[3:5] = "ba" → not palindrome ✗
            current.pop() → ["a","b"]
          Try end = 3: s[2:4] = "cb" → not palindrome ✗
          Try end = 4: s[2:5] = "cba" → not palindrome ✗
        current.pop() → ["a"]
      Try end = 2: s[1:3] = "bc" → not palindrome ✗
      Try end = 3: s[1:4] = "bcb" → palindrome ✓
        current = ["a", "bcb"]
        backtrack(4):
          start = 4
          Try end = 4: s[4:5] = "a" → palindrome ✓
            current = ["a", "bcb", "a"]
            backtrack(5):
              start = 5 === length → add to result
              result = [["a","b","c","b","a"], ["a","bcb","a"]]
            current.pop() → ["a","bcb"]
          current.pop() → ["a"]
        current.pop() → []
      Try end = 4: s[1:5] = "bcba" → not palindrome ✗
    current.pop() → []
  Try end = 1: s[0:2] = "ab" → not palindrome ✗
  Try end = 2: s[0:3] = "abc" → not palindrome ✗
  Try end = 3: s[0:4] = "abcb" → not palindrome ✗
  Try end = 4: s[0:5] = "abcba" → palindrome ✓
    current = ["abcba"]
    backtrack(5):
      start = 5 === length → add to result
      result = [["a","b","c","b","a"], ["a","bcb","a"], ["abcba"]]
    current.pop() → []

Result: [["a","b","c","b","a"], ["a","bcb","a"], ["abcba"]]

Visual Representation

Example 1: s = "abcba"

Backtracking tree:
  Start at position 0
    ├─ "a" (palindrome)
    │   ├─ "b" (palindrome)
    │   │   ├─ "c" (palindrome)
    │   │   │   ├─ "b" (palindrome)
    │   │   │   │   └─ "a" (palindrome) → ["a","b","c","b","a"] ✓
    │   │   └─ "bcb" (palindrome)
    │   │       └─ "a" (palindrome) → ["a","bcb","a"] ✓
    │   └─ "abcba" (palindrome) → ["abcba"] ✓

Partitions:
  1. ["a","b","c","b","a"]
  2. ["a","bcb","a"]
  3. ["abcba"]

Edge Cases

• Single character: Return [[s]] (one partition)
• All same characters: Many partitions (all substrings are palindromes)
• No palindromes except single chars: Only one partition (all single characters)
• Empty string: Return [[]] (one empty partition)
• Long palindromes: Can create fewer partitions

Important Notes

• Backtracking: Must explore all possible partitions
• Palindrome check: Can optimize with DP precomputation
• Recursive structure: Partition remaining string after each palindrome
• O(2^N) worst case: When all characters are the same
• DP optimization: Reduces palindrome check time from O(N) to O(1)

Why Backtracking Works

Key insight:

• We need to explore all possible ways to partition the string
• Backtracking systematically explores all possibilities
• For each position, we try all possible palindromic substrings
• This ensures we find all valid partitions

Optimal substructure:

• If we can partition s[start...end] as a palindrome, we can recursively partition s[end+1...]
• This creates the recursive structure

Related Problems

• Palindrome Partitioning II: Find minimum cuts
• Word Break II: Similar backtracking problem
• Restore IP Addresses: Similar partitioning problem
• Generate Parentheses: Different backtracking problem

Takeaways

• Backtracking explores all possible partitions
• Palindrome check for each substring
• Recursive structure partitions remaining string
• O(2^N) time in worst case
• DP optimization speeds up palindrome checks
• Classic backtracking problem with many applications