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).