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.