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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum cuts for palindrome partitioning

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

DSA C

int minCut(char* s) {
    int n = strlen(s);
    int dp[n+1];
    int pal[n][n];
    for (int i = 0; i < n; i++) {
        dp[i] = n - 1 - i;
        for (int j = 0; j <= i; j++) {
            if (s[i] == s[j] && (i - j < 2 || pal[j+1][i-1])) {
                pal[j][i] = 1;
                if (j == 0) dp[i] = 0;
                else if (dp[j-1] + 1 < dp[i]) dp[i] = dp[j-1] + 1;
            } else {
                pal[j][i] = 0;
            }
        }
    }
    return dp[n-1];
}

// Input string: "aab" 
// Call: minCut("aab")

A 1

B 0

C 2

D 3

💡 Hint

Think about how many cuts are needed to split "aab" into palindromes.

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

🧠 Conceptual

intermediate

Understanding the DP array in palindrome partitioning

In the palindrome partitioning minimum cuts problem, what does the dp array represent?

A dp[i] stores the maximum palindrome length ending at i

B dp[i] stores the minimum cuts needed for substring s[i..end]

C dp[i] stores the count of palindromes in s[0..i]

D dp[i] stores the minimum cuts needed for substring s[0..i]

💡 Hint

Think about what the problem asks: minimum cuts for prefixes of the string.

dp[i] holds the minimum number of cuts needed to partition the substring from the start up to index i into palindromes.

🔧 Debug

advanced

Identify the error in palindrome partitioning code

What error will the following code produce when run?

DSA C

int minCut(char* s) {
    int n = strlen(s);
    int dp[n];
    int pal[n][n];
    for (int i = 0; i < n; i++) {
        dp[i] = n - i;
        for (int j = 0; j <= i; j++) {
            if (s[i] == s[j] && (i - j < 2 || pal[j+1][i-1])) {
                pal[j][i] = 1;
                if (j == 0) dp[i] = 0;
                else if (dp[j-1] + 1 < dp[i]) dp[i] = dp[j-1] + 1;
            } else {
                pal[j][i] = 0;
            }
        }
    }
    return dp[n-1];
}

// Input: "aab"

A Compilation error due to uninitialized pal array

B Array index out of bounds error

C Returns incorrect minimum cuts

D No error, returns correct result

💡 Hint

Check the initialization and indexing of dp array.

dp[i] is initialized with n - i which can cause dp[j-1] access to be invalid when j=0, leading to out of bounds access.

❓ Predict Output

advanced

Output of minimum cuts for palindrome partitioning with repeated characters

What is the output of the minimum cuts function for the input string "ababbbabbababa"?

DSA C

int minCut(char* s) {
    int n = strlen(s);
    int dp[n];
    int pal[n][n];
    for (int i = 0; i < n; i++) {
        dp[i] = i;
        for (int j = 0; j <= i; j++) {
            if (s[i] == s[j] && (i - j < 2 || pal[j+1][i-1])) {
                pal[j][i] = 1;
                if (j == 0) dp[i] = 0;
                else if (dp[j-1] + 1 < dp[i]) dp[i] = dp[j-1] + 1;
            } else {
                pal[j][i] = 0;
            }
        }
    }
    return dp[n-1];
}

// Call: minCut("ababbbabbababa")

A 3

B 4

C 2

D 5

💡 Hint

Try to find the minimum cuts to split the string into palindromes.

The minimum cuts needed for "ababbbabbababa" is 3 based on palindrome partitions.

🧠 Conceptual

expert

Time complexity of palindrome partitioning minimum cuts algorithm

What is the time complexity of the dynamic programming solution for palindrome partitioning minimum cuts problem?

A O(n log n)

B O(n^2)

C O(n^3)

D O(n)

💡 Hint

Consider the nested loops and palindrome checks.

The solution uses two nested loops and palindrome checks inside, resulting in cubic time complexity.