Palindrome Partitioning

Introduction

Palindrome Partitioning is a classic backtracking problem where we are given a string s. The goal is to partition s such that every substring of the partition is a palindrome. We need to return all possible palindrome partitionings of s.

Example

For the string aab:

• a a b (All substrings are palindromes)
• aa b (All substrings are palindromes)

Output: [ ["a","a","b"], ["aa","b"] ]

The Backtracking Approach

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.

Why Backtracking?

We need to explore all possible ways to split the string. For a string of length n, there are 2^(n-1) ways to split it. A brute-force approach would check every single split, which is inefficient. Backtracking allows us to prune the search tree early: if a substring is not a palindrome, we stop exploring that path immediately.

Algorithm Steps

1. Base Case: If the current index start reaches the end of the string (start === s.length), we have found a valid partition. We add the current path (array of substrings) to the result.
2. Recursive Step: Iterate through the string from the current start index to the end (end). This loop represents the potential split points.
3. Check Palindrome: For each substring s.substring(start, end + 1), check if it is a palindrome.
4. Explore: If it is a palindrome, add it to the current path and recursively call the function with start = end + 1.
5. Backtrack: After the recursive call returns, remove the last element from path (undo the choice) so that the path is ready for the next iteration of the loop.

Implementation (TypeScript)

function partition(s: string): string[][] {
  const result: string[][] = [];
  const path: string[] = [];

  // Helper function to check if a substring is a palindrome
  const isPalindrome = (str: string, left: number, right: number): boolean => {
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  };

  // Main backtracking function
  const backtrack = (start: number) => {
    // Base case: if we've reached the end of the string
    if (start === s.length) {
      result.push([...path]); // Push a copy of the current path
      return;
    }

    // Try all possible end indices for the current partition
    for (let end = start; end < s.length; end++) {
      const substring = s.substring(start, end + 1);

      // If the substring is a palindrome, proceed
      if (isPalindrome(s, start, end)) {
        path.push(substring); // Choose
        backtrack(end + 1);   // Explore
        path.pop();           // Unchoose (Backtrack)
      }
    }
  };

  backtrack(0);
  return result;
}

Complexity Analysis

Time Complexity: O(N * 2^N)

1. Partitioning: There are 2^(N-1) ways to partition a string of length N.
2. Palindrome Check: In the worst case (e.g., all characters are the same, like "aaaaa"), we check every substring. Checking a substring takes O(N) time.
3. Total: O(N * 2^N).

Space Complexity: O(N * 2^N)

1. Result Storage: We store all possible partitions. In the worst case, there are 2^(N-1) partitions, and each partition can be up to length N. However, the space complexity is dominated by the recursion stack depth (O(N)) and the storage of the result itself.

Optimization: Precomputing Palindromes

Checking palindromes on the fly (isPalindrome) inside the loop can be expensive. We can optimize this by precomputing a 2D boolean table dp where dp[i][j] is true if s[i...j] is a palindrome.

DP Table Construction

We can fill this table using Dynamic Programming:

• Base Case: Single characters are palindromes (dp[i][i] = true).
• Transition: dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1].

This reduces the palindrome check from O(N) to O(1) per substring, improving the overall time complexity to O(N * 2^N) but with a much smaller constant factor.

Common Mistakes

1. Modifying the Result Array: Always push a copy of the path array to the result (result.push([...path])) rather than pushing the reference directly. Otherwise, all entries in the result will point to the same array and get modified later.
2. Forgetting Backtracking: If you don't path.pop() after the recursive call, the path array will accumulate elements, leading to incorrect results.
3. Incorrect Indexing: Be careful with string slicing. substring(start, end) includes start but excludes end. Since we are iterating end from start to length, we use end + 1 in the slice.

Real-World Applications

1. Word Break Problem: Similar to palindrome partitioning, determining if a string can be segmented into a dictionary of words.
2. DNA Sequencing: Breaking down long DNA sequences into palindromic segments for analysis.
3. Compiler Design: Analyzing string literals or identifiers for specific structural patterns.

Summary

Palindrome Partitioning is a quintessential backtracking problem. It teaches you how to:

• Structure a recursive function with a start index.
• Manage a path array to build solutions incrementally.
• Implement the crucial backtrack step (undoing choices).
• Prune the search tree by validating constraints (palindromes) early.