Palindrome Partitioning Using Backtracking in DSA Javascript

Mental Model

We want to split a string into parts where each part reads the same forwards and backwards. We try all splits step-by-step and keep only the good ones.

Analogy: Imagine cutting a ribbon into pieces where each piece is a perfect mirror image if folded. You try cutting at every spot and keep the cuts that make all pieces symmetrical.

s = "a b a c"
Partitions: ["a", "b", "a", "c"]
            ↑
Try cutting here -> check if substring is palindrome
If yes, keep and move forward

Dry Run Walkthrough

Input: string: "aab"

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

Step 1: Start from index 0, check substring "a"

"a" | "ab" (remaining)
Partitions so far: ["a"]

Why: Check if first letter alone is palindrome to start partition

Step 2: From index 1, check substring "a"

"a" | "a" | "b"
Partitions so far: ["a", "a"]

Why: Try next letter as palindrome part

Step 3: From index 2, check substring "b"

"a" | "a" | "b"
Partitions so far: ["a", "a", "b"]

Why: Last letter is palindrome, record this partition

Step 4: Backtrack to index 1, check substring "ab"

"a" | "ab"
Partitions so far: ["a"]

Why: "ab" is not palindrome, discard this path

Step 5: Backtrack to index 0, check substring "aa"

"aa" | "b"
Partitions so far: ["aa"]

Why: "aa" is palindrome, try next part

Step 6: From index 2, check substring "b"

"aa" | "b"
Partitions so far: ["aa", "b"]

Why: Last letter palindrome, record this partition

Result:

"a" | "a" | "b"
"aa" | "b"
All palindrome partitions found

Annotated Code

DSA Javascript

class PalindromePartitioning {
  constructor() {
    this.result = []
  }

  isPalindrome(s, left, right) {
    while (left < right) {
      if (s[left] !== s[right]) return false
      left++
      right--
    }
    return true
  }

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

    for (let end = start; end < s.length; end++) {
      if (this.isPalindrome(s, start, end)) {
        path.push(s.substring(start, end + 1))
        this.backtrack(s, end + 1, path)
        path.pop()
      }
    }
  }

  partition(s) {
    this.result = []
    this.backtrack(s, 0, [])
    return this.result
  }
}

// Driver code
const solver = new PalindromePartitioning()
const input = "aab"
const output = solver.partition(input)
for (const partition of output) {
  console.log(partition.join(' | '))
}

if (s[left] !== s[right]) return false

Check characters from both ends to confirm palindrome

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

If reached end of string, record current partition path

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

Try all substring ends from current start, proceed only if palindrome

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

Add current palindrome substring to path

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

Recurse to find partitions from next index

path.pop()

Backtrack by removing last substring to try other partitions

Output

a | a | b

aa | b

Complexity Analysis

Time: O(n * 2^n) because each character can start a new partition and palindrome checks happen for substrings

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

vs Alternative: Naive approach tries all partitions without palindrome checks, which is slower; backtracking prunes invalid paths early

Edge Cases

empty string

Returns [[]] representing the empty partition

DSA Javascript

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

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

Finds many partitions since every substring is palindrome

DSA Javascript

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

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

Partitions only single characters

DSA Javascript

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

When to Use This Pattern

When asked to split a string into palindrome parts and find all ways, use backtracking to explore all partitions and prune non-palindromes.

Common Mistakes

Mistake: Not checking palindrome before recursing, causing invalid partitions
Fix: Add palindrome check before adding substring to path and recursing

Mistake: Not backtracking (not removing last substring) after recursion, causing wrong results
Fix: Pop last substring from path after recursive call to try other partitions

Summary

Splits a string into all possible palindrome partitions using backtracking.

Use when you need to find all ways to break a string into palindrome substrings.

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

Practice

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

easy

A. To split a string into all possible palindrome substrings

B. To find the longest palindrome substring in a string

C. To reverse a string using recursion

D. To count the number of palindromes in a string

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 and keep only palindrome parts.

3. Final Answer:

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

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Backtracking tries all splits keeping palindromes only [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it only finds one palindrome partition
• Assuming it reverses the string

2. Which of the following is the correct way to check if a substring s.slice(start, end) is a palindrome in JavaScript?

easy

A. Check if s.slice(start, end) === s.slice(end, start).reverse()

B. Check if s.slice(start, end) === s.slice(start, end).split('').reverse().join('')

C. Check if s.slice(start, end) === s.reverse()

D. Check if s.slice(start, end) === s.split('').reverse()

Solution

1. Step 1: Extract substring correctly

   Use s.slice(start, end) to get substring from start to end-1.

2. Step 2: Check palindrome by reversing substring

   Reverse substring by splitting to array, reversing, then joining back to string.

3. Final Answer:

   Check if s.slice(start, end) === s.slice(start, end).split('').reverse().join('') -> Option B

4. Quick Check:

   Reverse substring and compare equals original [OK]

Hint: Reverse substring with split, reverse, join to check palindrome [OK]

Common Mistakes:

• Using slice with reversed indices (end before start)
• Trying to reverse string directly without split
• Comparing substring to reversed full string

3. What will be the output of the following code snippet?

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

function backtrack(s, start, path, result) {
  if (start === s.length) {
    result.push([...path]);
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    let sub = s.slice(start, end);
    if (isPalindrome(sub)) {
      path.push(sub);
      backtrack(s, end, path, result);
      path.pop();
    }
  }
}

let result = [];
backtrack('aab', 0, [], result);
console.log(result);

medium

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

B. [["aab"]]

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

D. [["aa", "ab"]]

Solution

1. Step 1: Check palindrome substrings in 'aab'

   Substrings: 'a', 'aa', 'aab', 'ab', 'b'. Palindromes are 'a', 'aa', 'b'.

2. Step 2: Backtracking builds partitions

   Partitions: ['a','a','b'] and ['aa','b'] are valid palindrome partitions.

3. Final Answer:

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

4. Quick Check:

   All palindrome partitions of 'aab' = [['a','a','b'], ['aa','b']] [OK]

Hint: Check all palindrome splits recursively to get partitions [OK]

Common Mistakes:

• Including non-palindrome substrings like 'ab'
• Missing the partition ['aa','b']
• Confusing output format with strings instead of arrays

4. Identify the bug in this backtracking code for palindrome partitioning:

function backtrack(s, start, path, result) {
  if (start > s.length) {
    result.push(path);
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    let sub = s.slice(start, end);
    if (sub === sub.split('').reverse().join('')) {
      path.push(sub);
      backtrack(s, end, path, result);
      path.pop();
    }
  }
}

medium

A. The path array should not be mutated with push and pop

B. The substring check is incorrect; should use a separate isPalindrome function

C. The base case condition should be start === s.length, not start > s.length

D. The for loop should start from end = start, not start + 1

Solution

1. Step 1: Analyze base case condition

   Base case triggers when start > s.length, but valid partitions end exactly at start === s.length.

2. Step 2: Correct base case to push result

   Change condition to start === s.length to add current path to result correctly.

3. Final Answer:

   The base case condition should be start === s.length, not start > s.length -> Option C

4. Quick Check:

   Base case triggers at string end index [OK]

Hint: Base case must match string length exactly to save partitions [OK]

Common Mistakes:

• Using > instead of === for base case
• Not pushing a copy of path (but not asked here)
• Starting loop incorrectly at start instead of start+1

5. Given the string "racecar", how many palindrome partitions will the backtracking algorithm find?

hard

A. 8

B. 6

C. 4

D. 10

Solution

1. Step 1: Identify palindrome substrings in 'racecar'

   Palindromes include all single characters 'r','a','c','e','c','a','r'; 'cec' (indices 2-4); 'aceca' (1-5); 'racecar' (whole).

2. Step 2: Count all palindrome partitions

   Valid partitions: ['racecar'], ['r','aceca','r'], ['r','a','cec','a','r'], ['r','a','c','e','c','a','r'], and others. Total 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Backtracking finds 10 palindrome partitions for 'racecar' [OK]

Hint: Count all palindrome splits including nested palindromes [OK]

Common Mistakes:

• Counting only single-character partitions
• Missing larger palindrome substrings like 'aceca'
• Assuming only 1 or 2 partitions exist