Palindrome Partitioning DP Minimum Cuts in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the minimum cuts array with the maximum possible cuts for each position.

DSA Typescript

const minCuts: number[] = new Array(n).fill([1]);

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

An - 1

B0

Cn

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing minCuts with 0 which assumes no cuts needed initially.

Using n instead of n-1 which is out of array bounds.

We initialize minCuts with the maximum cuts possible, which is n-1 cuts for a string of length n.

2fill in blank

medium

Complete the code to check if the substring from j to i is a palindrome using previously computed results.

DSA Typescript

if (s[j] === s[i] && (i - j < 2 || [1][j + 1][i - 1])) {

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

Apalindrome

BminCuts

Cdp

DisPalindrome

Attempts:

3 left

💡 Hint

Common Mistakes

Using minCuts or dp arrays which store cuts, not palindrome info.

Using undefined variable palindrome instead of isPalindrome.

The isPalindrome 2D array stores whether substring s[j+1..i-1] is a palindrome, which helps check s[j..i].

3fill in blank

hard

Fix the error in updating the minimum cuts when a palindrome substring is found.

DSA Typescript

minCuts[i] = j === 0 ? 0 : Math.min(minCuts[i], [1][j - 1] + 1);

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

AminCuts

BisPalindrome

Cdp

Dcuts

Attempts:

3 left

💡 Hint

Common Mistakes

Using isPalindrome or dp arrays which do not store cut counts.

Using an undefined variable cuts.

We update minCuts[i] by comparing with minCuts[j-1] + 1 cuts, not with palindrome or dp arrays.

4fill in blank

hard

Fill both blanks to correctly update the palindrome table and minimum cuts inside the nested loops.

DSA Typescript

isPalindrome[j][i] = true;
minCuts[i] = j === 0 ? 0 : Math.min(minCuts[i], [1][[2]] + 1);

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

AminCuts

Bj - 1

Ci - 1

DisPalindrome

Attempts:

3 left

💡 Hint

Common Mistakes

Using isPalindrome array to update minCuts which is incorrect.

Using i-1 instead of j-1 for previous cuts index.

We mark isPalindrome[j][i] true and update minCuts[i] using minCuts[j-1] + 1 cuts.

5fill in blank

hard

Fill all three blanks to complete the palindrome partitioning minimum cuts function.

DSA Typescript

function minCut(s: string): number {
  const n = s.length;
  const minCuts = new Array(n).fill([1]);
  const isPalindrome: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j <= i; j++) {
      if (s[j] === s[i] && (i - j < 2 || isPalindrome[j + 1][i - 1])) {
        isPalindrome[j][i] = true;
        minCuts[i] = j === 0 ? 0 : Math.min(minCuts[i], [2][[3]] + 1);
      }
    }
  }
  return minCuts[n - 1];
}

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

An - 1

BminCuts

Cj - 1

DisPalindrome

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing minCuts with 0 or n instead of n-1.

Using isPalindrome array to update minCuts.

Using wrong index like i-1 instead of j-1 for previous cuts.

Initialize minCuts with n-1, update minCuts[i] using minCuts[j-1] + 1 cuts for palindrome substrings.