Palindrome Partitioning Using Backtracking in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a substring is a palindrome.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A(right)

B[left]

C[right]

D(left)

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses instead of brackets for string indexing.

Comparing s[left] with s[left] instead of s[right].

We compare characters at positions 'left' and 'right' to check palindrome. So s[left] !== s[right] is correct.

2fill in blank

medium

Complete the code to add a substring to the current partition.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Apush

Bpop

Cslice

Dsplice

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push to add elements.

Using slice or splice which do not add elements.

We add the substring to currentPartition using push before recursive call.

3fill in blank

hard

Fix the error in the base case condition to stop recursion correctly.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A<=

B<

C>

D===

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than or greater than instead of equality.

Using <= or >= which may cause incorrect recursion.

The base case is when start equals s.length, meaning we have partitioned the whole string.

4fill in blank

hard

Fill both blanks to complete the main function that starts backtracking.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A0

Bresult

Cs.length

DcurrentPartition

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from s.length which skips processing.

Returning currentPartition instead of result.

We start backtracking from index 0 and return the result array.

5fill in blank

hard

Fill all three blanks to complete the palindrome partitioning code with backtracking.

DSA Typescript

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

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

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

Drag options to blanks, or click blank then click option'

A<

Bpush

C0

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= in while loop causing extra checks.

Using pop instead of push to add substring.

Starting backtracking from 1 instead of 0.

Use '<' in palindrome check loop, push to add substring, and start backtracking from 0.