Palindrome Partitioning Using Backtracking in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Partitioning Result

What is the output of the following JavaScript code that finds all palindrome partitions of the string 'aab'?

DSA Javascript

function isPalindrome(s) {
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

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

function palindromePartition(s) {
  const result = [];
  backtrack(s, 0, [], result);
  return result;
}

console.log(palindromePartition('aab'));

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

B [["aa","b"]]

C [["a","a","b"]]

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

💡 Hint

Think about all ways to split the string where each part is a palindrome.

The code finds all partitions of 'aab' where each substring is a palindrome. 'a', 'a', 'b' are all palindromes, and 'aa' is also a palindrome, so the partitions are ["a","a","b"] and ["aa","b"].

🧠 Conceptual

intermediate

Understanding Backtracking in Palindrome Partitioning

In palindrome partitioning using backtracking, what is the main reason for using backtracking?

A To explore all possible substring partitions and revert choices to find all palindrome partitions.

B To sort the string before partitioning.

C To store all substrings permanently without removing any.

D To convert the string into a number for easier processing.

💡 Hint

Backtracking helps when you need to try many options and undo some choices.

Backtracking explores all possible partitions by choosing substrings and then undoing those choices to try others, ensuring all palindrome partitions are found.

🔧 Debug

advanced

Identify the Error in Palindrome Partitioning Code

What error will the following code produce when run, and why?

DSA Javascript

function isPalindrome(s) {
  for (let i = 0; i < s.length / 2; i++) {
    if (s[i] !== s[s.length - i - 1]) return false;
  }
  return true;
}

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

function palindromePartition(s) {
  const result = [];
  backtrack(s, 0, [], result);
  return result;
}

console.log(palindromePartition('aba'));

A TypeError because s[s.length - i] is undefined when i=0

B SyntaxError due to missing semicolon

C Returns incorrect partitions because isPalindrome logic is wrong

D Runs correctly and outputs [['a','b','a'], ['aba']]

💡 Hint

Check the palindrome check logic carefully, especially the index used.

The code uses s[s.length - i] instead of s[s.length - i - 1], so it compares wrong characters and returns false negatives, causing incorrect partitions.

❓ Predict Output

advanced

Output of Palindrome Partitioning with Repeated Characters

What is the output of the following code for palindrome partitioning of 'aaa'?

DSA Javascript

function isPalindrome(s) {
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

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

function palindromePartition(s) {
  const result = [];
  backtrack(s, 0, [], result);
  return result;
}

console.log(palindromePartition('aaa'));

A [["a","a","a"],["aa","a"]]

B [["a","a","a"],["a","aa"],["aa","a"],["aaa"]]

C [["aaa"]]

D [["a","aa"]]

💡 Hint

Consider all ways to split 'aaa' into palindromes.

All single characters 'a' are palindromes, 'aa' is palindrome, and 'aaa' is palindrome. So all partitions with these substrings are included.

🧠 Conceptual

expert

Time Complexity of Palindrome Partitioning Using Backtracking

What is the time complexity of palindrome partitioning using backtracking for a string of length n, considering all possible partitions?

A O(n * 2^n) because there are 2^(n-1) possible partitions and palindrome checks take O(n)

B O(n^2) because we only check substrings once

C O(n!) because permutations of substrings are considered

D O(2^n) because palindrome checks are constant time

💡 Hint

Think about how many ways to partition and how palindrome checks add up.

There are about 2^(n-1) ways to partition a string. Each palindrome check can take up to O(n), so total complexity is O(n * 2^n).

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