Palindrome Partitioning DP Minimum Cuts in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum cuts for palindrome partitioning

What is the output of the following TypeScript code that calculates the minimum cuts needed to partition the string into palindromes?

DSA Typescript

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 end = 0; end < n; end++) {
    let minCuts = end;
    for (let start = 0; start <= end; start++) {
      if (s[start] === s[end] && (end - start < 2 || palindrome[start + 1][end - 1])) {
        palindrome[start][end] = true;
        minCuts = start === 0 ? 0 : Math.min(minCuts, dp[start - 1] + 1);
      }
    }
    dp[end] = minCuts;
  }
  return dp[n - 1];
}

console.log(minCut("aab"));

A 1

B 0

C 2

D 3

💡 Hint

Think about how the string "aab" can be split into palindromes with minimum cuts.

The string "aab" can be split into "aa" and "b", both palindromes, so only 1 cut is needed.

🧠 Conceptual

intermediate

Understanding the role of the palindrome table

In the palindrome partitioning DP solution, what is the main purpose of the 2D boolean array 'palindrome'?

A To store whether the substring s[start..end] is a palindrome

B To count the number of palindrome substrings in s

C To keep track of minimum cuts needed for each substring

D To store the length of the longest palindrome substring

💡 Hint

Consider what information is needed to decide if a substring is palindrome quickly.

The 'palindrome' table stores true or false for each substring indicating if it is a palindrome, which helps avoid recomputing palindrome checks.

❓ Predict Output

advanced

Minimum cuts for a complex palindrome partitioning

What is the output of the following TypeScript code for the input string "abccbc"?

DSA Typescript

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 end = 0; end < n; end++) {
    let minCuts = end;
    for (let start = 0; start <= end; start++) {
      if (s[start] === s[end] && (end - start < 2 || palindrome[start + 1][end - 1])) {
        palindrome[start][end] = true;
        minCuts = start === 0 ? 0 : Math.min(minCuts, dp[start - 1] + 1);
      }
    }
    dp[end] = minCuts;
  }
  return dp[n - 1];
}

console.log(minCut("abccbc"));

A 0

B 2

C 3

D 1

💡 Hint

Try to find palindrome partitions with minimum cuts for "abccbc".

The minimum cuts needed are 2, for example: "a" | "bccb" | "c".

🔧 Debug

advanced

Identify the error in palindrome partitioning code

What error will the following TypeScript code produce when run?

DSA Typescript

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 end = 0; end < n; end++) {
    let minCuts = end;
    for (let start = 0; start <= end; start++) {
      if (s[start] === s[end] && (end - start < 2 || palindrome[start + 1][end - 1])) {
        palindrome[start][end] = true;
        minCuts = start === 0 ? 0 : Math.min(minCuts, dp[start] + 1);
      }
    }
    dp[end] = minCuts;
  }
  return dp[n - 1];
}

console.log(minCut("abc"));

A No error, outputs 2

B TypeError: Cannot read property of undefined

C SyntaxError due to missing colon

D Wrong output: 1 instead of 2

💡 Hint

Check the dp index used inside Math.min for updating minCuts.

The code uses dp[start] instead of dp[start - 1], causing incorrect minimum cuts calculation.

🚀 Application

expert

Minimum cuts for palindrome partitioning of a long string

Given the string "noonabbad", what is the minimum number of cuts needed to partition it into palindromes?

A 3

B 1

C 2

D 0

💡 Hint

Try to find palindrome substrings like "noon", "abba", and "d".

The string can be partitioned as "noon" | "abba" | "d", requiring 2 cuts.

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