Palindrome Partitioning Using Backtracking in DSA Typescript

Mental Model

We want to split a word into parts where each part reads the same forwards and backwards. We try all ways to cut the word and keep only the good ones.

Analogy: Imagine cutting a chocolate bar into pieces where each piece is perfectly symmetrical. You try every possible way to break it and keep the symmetrical pieces only.

s = "a b a c"
Partitions: ["a", "b", "a", "c"]
           ["a", "b", "a c"] (invalid)
           ["aba", "c"]
           ↑ start here, try cuts

Dry Run Walkthrough

Input: string: "aab"

Goal: Find all ways to split "aab" so each part is a palindrome

Step 1: Check substring "a" (index 0 to 0), it is palindrome, add to current partition

["a"] ↑ start at index 1 in "aab"

Why: We try the smallest piece first to build partitions

Step 2: Check substring "a" (index 1 to 1), palindrome, add to current partition

["a", "a"] ↑ start at index 2 in "aab"

Why: Continue cutting next palindrome piece

Step 3: Check substring "b" (index 2 to 2), palindrome, add to current partition

["a", "a", "b"] ↑ start at index 3 (end)

Why: Reached end, current partition is valid

Step 4: Backtrack to last cut, remove "b", try longer substring "ab" (index 1 to 2), not palindrome, skip

["a", "a"] ↑ start at index 2

Why: Try other cuts after backtracking

Step 5: Backtrack to first cut, remove "a", try substring "aa" (index 0 to 1), palindrome, add

["aa"] ↑ start at index 2

Why: Try bigger palindrome piece at start

Step 6: Check substring "b" (index 2 to 2), palindrome, add

["aa", "b"] ↑ start at index 3 (end)

Why: Reached end, current partition is valid

Result:

["a", "a", "b"]
["aa", "b"]

Annotated Code

DSA Typescript

class PalindromePartitioning {
  private isPalindrome(s: string, left: number, right: number): boolean {
    while (left < right) {
      if (s[left] !== s[right]) return false; // mismatch means not palindrome
      left++; // move inward
      right--;
    }
    return true; // all matched
  }

  private backtrack(s: string, start: number, path: string[], result: string[][]): void {
    if (start === s.length) {
      result.push([...path]); // found valid partition
      return;
    }

    for (let end = start; end < s.length; end++) {
      if (this.isPalindrome(s, start, end)) {
        path.push(s.substring(start, end + 1)); // add palindrome piece
        this.backtrack(s, end + 1, path, result); // recurse for next part
        path.pop(); // backtrack to try other cuts
      }
    }
  }

  public partition(s: string): string[][] {
    const result: string[][] = [];
    this.backtrack(s, 0, [], result);
    return result;
  }
}

// Driver code
const solver = new PalindromePartitioning();
const input = "aab";
const partitions = solver.partition(input);
for (const p of partitions) {
  console.log(p.join(", "));
}

if (s[left] !== s[right]) return false; // mismatch means not palindrome

check if current substring is palindrome by comparing ends

if (start === s.length) { result.push([...path]); return; }

if reached end of string, save current partition

for (let end = start; end < s.length; end++) { if (this.isPalindrome(s, start, end)) {

try all substring ends from start, only proceed if palindrome

path.push(s.substring(start, end + 1));

add current palindrome substring to path

this.backtrack(s, end + 1, path, result);

recurse to find partitions for remaining string

path.pop();

remove last substring to backtrack and try other options

Output

a, a, b

aa, b

Complexity Analysis

Time: O(n * 2^n) because each character can be cut or not, and palindrome checks take O(n)

Space: O(n) for recursion stack and path storage

vs Alternative: Naive approach tries all partitions without pruning palindrome checks, which is slower

Edge Cases

empty string

returns [[]], a list containing one empty partition

DSA Typescript

if (start === s.length) { result.push([...path]); return; }

string with all same characters, e.g. "aaa"

returns all possible palindrome partitions including single chars and longer palindromes

DSA Typescript

if (this.isPalindrome(s, start, end)) {

string with no palindrome longer than 1, e.g. "abc"

returns partitions with single characters only

DSA Typescript

if (this.isPalindrome(s, start, end)) {

When to Use This Pattern

When asked to find all ways to split a string into palindrome parts, use backtracking to try all cuts and check palindrome validity.

Common Mistakes

Mistake: Not backtracking properly by forgetting to remove last added substring after recursion
Fix: Always pop the last substring after recursive call to explore other partitions

Summary

Splits a string into all possible palindrome partitions using backtracking.

Use when you need all palindrome partitions of a string.

Try every cut, keep only palindrome pieces, and backtrack to explore all options.