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.

Practice

1. What does the "Palindrome Partitioning DP Minimum Cuts" problem aim to find for a given string s?

easy

A. The minimum number of cuts needed to partition s into palindromic substrings

B. The maximum length of a palindrome substring in s

C. The total number of palindrome substrings in s

D. The longest palindrome substring in s

Solution

1. Step 1: Understand the problem goal

   The problem asks for the fewest cuts needed to split the string into parts where each part is a palindrome.

2. Step 2: Clarify what minimum cuts mean

   Minimum cuts means the smallest number of splits to make all parts palindromes.

3. Final Answer:

   The minimum number of cuts needed to partition s into palindromic substrings -> Option A

4. Quick Check:

   Minimum cuts = minimum splits for palindrome parts [OK]

Hint: Focus on splitting string into palindrome parts with fewest cuts [OK]

Common Mistakes:

• Confusing minimum cuts with longest palindrome substring
• Counting total palindrome substrings instead of cuts
• Thinking about maximum palindrome length

2. Which of the following TypeScript function signatures correctly represents a function to compute minimum palindrome partition cuts for a string s?

easy

A. function minCut(s: string): string[]

B. function minCut(s: number): string

C. function minCut(s: string): number

D. function minCut(s: boolean): number

Solution

1. Step 1: Identify input and output types

   Input is a string s, output is a number representing minimum cuts.

2. Step 2: Match correct signature

   Only function minCut(s: string): number matches input string and numeric output.

3. Final Answer:

   function minCut(s: string): number -> Option C

4. Quick Check:

   Input string, output number for cuts [OK]

Hint: Input string, output number for minimum cuts [OK]

Common Mistakes:

• Using wrong input type like number or boolean
• Returning array or string instead of number
• Mixing input and output types

3. What is the output of the following TypeScript code for input "aab"?

function minCut(s: string): number {
  const n = s.length;
  const dp = new Array(n).fill(0);
  const palindrome = Array.from({ length: n }, () => new Array(n).fill(false));

  for (let i = 0; i < n; i++) {
    let minCuts = i;
    for (let j = 0; j <= i; j++) {
      if (s[j] === s[i] && (i - j < 2 || palindrome[j + 1][i - 1])) {
        palindrome[j][i] = true;
        minCuts = j === 0 ? 0 : Math.min(minCuts, dp[j - 1] + 1);
      }
    }
    dp[i] = minCuts;
  }
  return dp[n - 1];
}
console.log(minCut("aab"));

medium

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace palindrome checks for "aab"

   Substrings: "a" (palindrome), "aa" (palindrome), "b" (palindrome). Minimum cuts for "aab" is 1 (cut between "aa" and "b").

2. Step 2: Check dp array updates

   dp[0]=0 ("a"), dp[1]=0 ("aa"), dp[2]=1 (cut before "b").

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Minimum cuts for "aab" = 1 [OK]

Hint: Check palindrome substrings and update dp for minimum cuts [OK]

Common Mistakes:

• Assuming no cuts needed for "aab"
• Counting total palindromes instead of cuts
• Incorrect dp index updates

4. Identify the bug in this TypeScript code snippet for minimum palindrome partition cuts:

function minCut(s: string): number {
  const n = s.length;
  const dp = new Array(n).fill(0);
  const palindrome = Array.from({ length: n }, () => new Array(n).fill(false));

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

medium

A. dp[i] should be initialized to 0 instead of i

B. Inner loop should run from j = 0 to j <= i

C. palindrome array initialization is incorrect

D. dp[j] should be dp[j - 1] when updating dp[i]

Solution

1. Step 1: Analyze dp update logic

   When substring s[j..i] is palindrome, dp[i] should consider dp[j-1] + 1 cuts, not dp[j] + 1.

2. Step 2: Identify correct index for dp

   dp[j-1] represents cuts before substring start; dp[j] is incorrect and causes off-by-one error.

3. Final Answer:

   dp[j] should be dp[j - 1] when updating dp[i] -> Option D

4. Quick Check:

   Use dp[j-1] for correct minimum cuts [OK]

Hint: Use dp[j-1] when substring starts at j to avoid off-by-one error [OK]

Common Mistakes:

• Using dp[j] instead of dp[j-1]
• Incorrect loop bounds causing missed palindromes
• Wrong initialization of dp array

5. Given the string "abccbc", what is the minimum number of cuts needed to partition it into palindromic substrings using the DP approach?

hard

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Identify palindromic substrings in "abccbc"

   Palindromes include "a", "b", "cc", "bcb", "c". Partitioning as "a" | "bccb" | "c" is possible with 2 cuts.

2. Step 2: Calculate minimum cuts

   Minimum cuts = 2 because splitting into "a" | "bccb" | "c" yields all palindromes with 2 cuts.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Minimum cuts for "abccbc" = 2 [OK]

Hint: Look for largest palindrome substrings to minimize cuts [OK]

Common Mistakes:

• Assuming 0 cuts because string is not fully palindrome
• Counting each character as separate palindrome causing more cuts
• Missing palindrome "bccb" in middle