Palindrome Partitioning DP Minimum Cuts in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a substring is a palindrome.

DSA C

int isPalindrome(char* s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return [1];
        }
        start++;
        end--;
    }
    return 1;
}

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

A2

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 1 instead of 0 on mismatch

Not returning immediately on mismatch

If characters at start and end don't match, the substring is not a palindrome, so return 0 (false).

2fill in blank

medium

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

DSA C

for (int i = 0; i < n; i++) {
    minCuts[i] = [1];
}

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

A0

Bi

Cn - 1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 0 which is incorrect

Using n instead of i

Initialize minCuts[i] with i, the maximum cuts needed if every character is a separate palindrome.

3fill in blank

hard

Fix the error in the code that updates minimum cuts when a palindrome substring is found.

DSA C

if (isPalindrome(s, j, i)) {
    if (j == 0) {
        minCuts[i] = 0;
    } else {
        minCuts[i] = [1];
    }
}

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

AminCuts[i] + 1

BminCuts[j] + 1

CminCuts[j - 1] + 1

DminCuts[i - 1] + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using minCuts[i] + 1 causes infinite increase

Using minCuts[j] instead of minCuts[j-1]

If substring s[j..i] is palindrome, minimum cuts at i can be updated as minCuts[j-1] + 1.

4fill in blank

hard

Fill both blanks to complete the nested loops for DP minimum cuts calculation.

DSA C

for (int i = 1; i < n; i++) {
    for (int j = 0; j <= [1]; j++) {
        if (isPalindrome(s, j, i)) {
            if (j == 0) {
                minCuts[i] = 0;
            } else {
                minCuts[i] = min(minCuts[i], [2]);
            }
        }
    }
}

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

Ai

Bj - 1

Ci - 1

DminCuts[j - 1] + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Looping j beyond i

Using wrong expression for minCuts update

Inner loop runs j from 0 to i. Update minCuts[i] with minimum of current and minCuts[j-1]+1.

5fill in blank

hard

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

DSA C

int minCut(char* s) {
    int n = strlen(s);
    int minCuts[n];
    for (int i = 0; i < n; i++) {
        minCuts[i] = [1];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= [2]; j++) {
            if (isPalindrome(s, j, i)) {
                if (j == 0) {
                    minCuts[i] = 0;
                } else {
                    minCuts[i] = min(minCuts[i], [3]);
                }
            }
        }
    }
    return minCuts[n - 1];
}

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

Ai

Bn - 1

CminCuts[j - 1] + 1

DminCuts[i - 1] + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing minCuts with wrong value

Looping j incorrectly

Updating minCuts[i] with wrong expression

Initialize minCuts[i] = i; inner loop j runs to i; update minCuts[i] with minCuts[j-1]+1.