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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Partitioning for 'aab'

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

DSA Typescript

function isPalindrome(s: string, left: number, right: number): boolean {
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

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

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

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

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

B [["aab"]]

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

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

💡 Hint

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

The code finds all partitions where each substring is a palindrome. For 'aab', the valid partitions are ['a','a','b'] and ['aa','b'].

🧠 Conceptual

intermediate

Number of Palindrome Partitions for 'racecar'

How many palindrome partitions does the string 'racecar' have using backtracking?

A 4

B 10

C 6

D 12

💡 Hint

Consider all ways to split 'racecar' into palindromic substrings.

The string 'racecar' has 4 palindrome partitions including single letters and larger palindromes like 'racecar' itself.

🔧 Debug

advanced

Identify the Bug in Palindrome Partitioning Code

What error does the following TypeScript code produce when run with input 'abc'?

DSA Typescript

function isPalindrome(s: string, left: number, right: number): boolean {
  while (left <= right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

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

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

console.log(partition('abc'));

A SyntaxError: Unexpected token

B No error, outputs [['a','b','c']]

C TypeError: s.substring is not a function

D RangeError: Maximum call stack size exceeded

💡 Hint

Check the palindrome check condition carefully.

The code runs correctly and outputs [['a','b','c']] because each single character is a palindrome.

❓ Predict Output

advanced

Output of Palindrome Partitioning for 'aaa'

What is the output of the following TypeScript code that partitions 'aaa' into palindromes?

DSA Typescript

function isPalindrome(s: string, left: number, right: number): boolean {
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

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

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

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

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

B [["aaa"]]

C [["a","a","a"],["a","aa"],["aa","a"],["aaa"]]

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

💡 Hint

Consider all palindrome substrings including overlapping ones.

The code finds all palindrome partitions including single letters, pairs, and the whole string.

🧠 Conceptual

expert

Time Complexity of Palindrome Partitioning Using Backtracking

What is the time complexity of the palindrome partitioning algorithm using backtracking for a string of length n?

A O(2^n)

B O(n^3)

C O(n!)

D O(n * 2^n)

💡 Hint

Consider the number of partitions and palindrome checks.

The algorithm explores all partitions (up to 2^(n-1)) and checks palindrome in O(n), leading to O(n * 2^n).

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