Palindrome Partitioning Using Backtracking in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Partitioning for "aab"

What is the output of the following C code that prints all palindrome partitions of the string "aab"?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(char *str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end])
            return false;
        start++;
        end--;
    }
    return true;
}

void backtrack(char *s, int start, int len, char result[][100], int resultSize) {
    if (start == len) {
        for (int i = 0; i < resultSize; i++) {
            printf("%s", result[i]);
            if (i != resultSize - 1) printf("|");
        }
        printf("\n");
        return;
    }

    for (int end = start; end < len; end++) {
        if (isPalindrome(s, start, end)) {
            int substrLen = end - start + 1;
            strncpy(result[resultSize], s + start, substrLen);
            result[resultSize][substrLen] = '\0';
            backtrack(s, end + 1, len, result, resultSize + 1);
        }
    }
}

int main() {
    char s[] = "aab";
    int len = strlen(s);
    char result[100][100];
    backtrack(s, 0, len, result, 0);
    return 0;
}

A

a|ab
aa|b

B

a|a|b
aab

C

a|a|b
aa|b

D

aa|b
a|b

💡 Hint

Check all substrings that are palindromes and print partitions separated by '|'.

The code finds all palindrome partitions of "aab". The partitions are: "a|a|b" and "aa|b".

🧠 Conceptual

intermediate

Number of Palindrome Partitions for "abc"

How many palindrome partitions does the string "abc" have?

A 0

B 1

C 2

D 3

💡 Hint

Each single character is a palindrome itself.

The only palindrome partition is "a|b|c", since no consecutive characters form a palindrome. Thus, there is 1 palindrome partition.

❓ Predict Output

advanced

Output of Palindrome Partitioning for "racecar"

What is the output of the following C code that prints all palindrome partitions of the string "racecar"?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(char *str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end])
            return false;
        start++;
        end--;
    }
    return true;
}

void backtrack(char *s, int start, int len, char result[][100], int resultSize) {
    if (start == len) {
        for (int i = 0; i < resultSize; i++) {
            printf("%s", result[i]);
            if (i != resultSize - 1) printf("|");
        }
        printf("\n");
        return;
    }

    for (int end = start; end < len; end++) {
        if (isPalindrome(s, start, end)) {
            int substrLen = end - start + 1;
            strncpy(result[resultSize], s + start, substrLen);
            result[resultSize][substrLen] = '\0';
            backtrack(s, end + 1, len, result, resultSize + 1);
        }
    }
}

int main() {
    char s[] = "racecar";
    int len = strlen(s);
    char result[100][100];
    backtrack(s, 0, len, result, 0);
    return 0;
}

A

r|a|c|e|c|a|r
r|a|cec|a|r
r|aceca|r
racecar

B

r|a|c|e|c|a|r
ra|cec|ar
racecar

C

r|a|c|e|c|a|r
r|aceca|r
racecar

D

racecar
r|a|c|e|c|a|r
r|a|cec|a|r

💡 Hint

Look for all palindrome substrings including single letters and longer palindromes like "cec", "aceca", and "racecar" itself.

The code prints all palindrome partitions of "racecar". The partitions include all single letters, and longer palindromes like "cec", "aceca", and the full "racecar".

🔧 Debug

advanced

Identify the error in palindrome check function

What error will the following palindrome check function cause when called with start > end?

DSA C

bool isPalindrome(char *str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end])
            return false;
        start++;
        end--;
    }
    return true;
}

// Called as isPalindrome(s, 3, 2);

A Causes infinite loop

B Returns false without error

C Causes out-of-bounds access

D Returns true without error

💡 Hint

Check the while loop condition and what happens if start is greater than end initially.

If start > end initially, the while loop condition is false, so the function returns true immediately. This is correct behavior for empty or invalid substring.

🚀 Application

expert

Minimum Cuts for Palindrome Partitioning

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

A 3

B 5

C 4

D 6

💡 Hint

Use dynamic programming or backtracking to find minimum cuts for palindrome partitions.

The minimum cuts needed for "ababbbabbababa" is 3. One optimal partition is: "a|babbbab|b|ababa".