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.

Practice

1. What is the main goal of palindrome partitioning using backtracking?

easy

A. To reverse the string and check if it is a palindrome

B. To find the longest palindrome substring in a string

C. To count the number of palindromes in a string

D. To split a string into all possible palindrome substrings

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing a string into parts where each part is a palindrome.

2. Step 2: Role of backtracking

   Backtracking helps explore all possible ways to split the string into palindrome parts.

3. Final Answer:

   To split a string into all possible palindrome substrings -> Option D

4. Quick Check:

   Palindrome partitioning = all palindrome splits [OK]

Hint: Backtracking explores all palindrome splits step-by-step [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it only counts palindromes instead of listing partitions
• Assuming it just reverses the string

2. Which of the following TypeScript function signatures correctly represents a backtracking function for palindrome partitioning?

easy

A. function backtrack(s: number[], start: string, path: string[], result: string[][]): string

B. function backtrack(s: string, start: number, path: string, result: string[]): boolean

C. function backtrack(s: string, start: number, path: string[], result: string[][]): void

D. function backtrack(s: string[], start: number, path: string[], result: string[][]): number

Solution

1. Step 1: Analyze parameter types

   The string to partition is 's: string', start index is 'number', path is an array of strings, and result is an array of string arrays.

2. Step 2: Check return type

   Backtracking functions usually return void because they build results by modifying the result array.

3. Final Answer:

   function backtrack(s: string, start: number, path: string[], result: string[][]): void -> Option C

4. Quick Check:

   Correct signature = function backtrack(s: string, start: number, path: string[], result: string[][]): void [OK]

Hint: Backtracking returns void and uses arrays for path and result [OK]

Common Mistakes:

• Using wrong parameter types like number[] instead of string
• Returning boolean or number instead of void
• Passing path as string instead of string[]

3. What will be the output of the following TypeScript code snippet for palindrome partitioning of string "aab"?

function isPalindrome(s: string): boolean {
  return s === s.split('').reverse().join('');
}

function backtrack(s: string, start: number, path: string[], result: string[][]): void {
  if (start === s.length) {
    result.push([...path]);
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    const substr = s.substring(start, end);
    if (isPalindrome(substr)) {
      path.push(substr);
      backtrack(s, end, path, result);
      path.pop();
    }
  }
}

const result: string[][] = [];
backtrack("aab", 0, [], result);
console.log(result);

medium

A. [["aa", "ab"]]

B. [["a", "a", "b"], ["aa", "b"]]

C. [["a", "ab"]]

D. [["aab"]]

Solution

1. Step 1: Identify palindrome substrings in "aab"

   "a" and "aa" are palindromes; "b" is a palindrome; "ab" and "aab" are not.

2. Step 2: Trace backtracking calls

   Partitions found are ["a", "a", "b"] and ["aa", "b"] added to result.

3. Final Answer:

   [["a", "a", "b"], ["aa", "b"]] -> Option B

4. Quick Check:

   All palindrome splits of "aab" = [["a", "a", "b"], ["aa", "b"]] [OK]

Hint: Check all palindrome substrings and backtrack all splits [OK]

Common Mistakes:

• Including non-palindrome substrings like "ab"
• Missing the "aa" substring partition
• Returning only one partition instead of all

4. Identify the bug in the following backtracking code for palindrome partitioning and select the fix:

function isPalindrome(s: string): boolean {
  return s === s.split('').reverse().join('');
}

function backtrack(s: string, start: number, path: string[], result: string[][]): void {
  if (start > s.length) {
    result.push([...path]);
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    const substr = s.substring(start, end);
    if (isPalindrome(substr)) {
      path.push(substr);
      backtrack(s, end, path, result);
      path.pop();
    }
  }
}

medium

A. Change condition to if (start === s.length) to stop recursion correctly

B. Change substring to slice for correct substring extraction

C. Remove path.pop() to keep all partitions

D. Change for loop to end < s.length to avoid out of bounds

Solution

1. Step 1: Analyze base case condition

   Condition 'start > s.length' allows start to be s.length + 1, which is invalid index.

2. Step 2: Correct base case for recursion end

   It should be 'start === s.length' to indicate full string processed and add path to result.

3. Final Answer:

   Change condition to if (start === s.length) to stop recursion correctly -> Option A

4. Quick Check:

   Base case must be start === s.length [OK]

Hint: Base case triggers when start equals string length [OK]

Common Mistakes:

• Using > instead of === in base case
• Removing path.pop() causing wrong partitions
• Changing substring method unnecessarily

5. Given the string "racecar", which of the following is NOT a valid palindrome partitioning produced by a backtracking algorithm?

hard

A. ["rac", "ecar"]

B. ["racecar"]

C. ["r", "a", "c", "e", "c", "a", "r"]

D. ["r", "aceca", "r"]

Solution

1. Step 1: Check palindrome validity of each substring

   "rac" and "ecar" are not palindromes; others are single letters or full palindrome.

2. Step 2: Confirm valid partitions

   Partitions with only palindrome substrings are valid; those with non-palindromes are invalid.

3. Final Answer:

   ["rac", "ecar"] -> Option A

4. Quick Check:

   Non-palindrome substrings invalidate partition [OK]

Hint: Check each substring is palindrome to validate partition [OK]

Common Mistakes:

• Assuming any split is valid without palindrome check
• Confusing full string palindrome with partial substrings
• Ignoring single character substrings as palindromes