Palindrome Partitioning Using Backtracking 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++

bool isPalindrome(const string &s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return [1];
        }
        start++;
        end--;
    }
    return true;
}

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

Afalse

Btrue

Cstart

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true when characters don't match.

Returning start or end instead of a boolean.

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

2fill in blank

medium

Complete the code to add the current substring to the path vector.

DSA C++

void backtrack(const string &s, int start, vector<string> &path, vector<vector<string>> &result) {
    if (start == s.size()) {
        result.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); end++) {
        if (isPalindrome(s, start, end)) {
            path.[1](s.substr(start, end - start + 1));
            backtrack(s, end + 1, path, result);
            path.pop_back();
        }
    }
}

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

Aappend

Badd

Cinsert

Dpush_back

Attempts:

3 left

💡 Hint

Common Mistakes

Using append which is not valid for vector.

Using insert without specifying position.

In C++, vector uses push_back to add elements at the end.

3fill in blank

hard

Fix the error in the base case condition to check if we reached the end of the string.

DSA C++

void backtrack(const string &s, int start, vector<string> &path, vector<vector<string>> &result) {
    if (start [1] s.size()) {
        result.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); end++) {
        if (isPalindrome(s, start, end)) {
            path.push_back(s.substr(start, end - start + 1));
            backtrack(s, end + 1, path, result);
            path.pop_back();
        }
    }
}

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

A>

B==

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or < which can cause out-of-bound errors.

Using != which is incorrect for this base case.

We want to check if start reached the string length, meaning all characters are processed.

4fill in blank

hard

Fill both blanks to create a map of substring lengths to substrings that are palindromes.

DSA C++

unordered_map<int, vector<string>> palindromeMap;
for (int i = 0; i < s.size(); i++) {
    for (int j = i; j < s.size(); j++) {
        if (isPalindrome(s, i, j)) {
            palindromeMap[[1]].push_back(s.substr(i, [2]));
        }
    }
}

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

Aj - i + 1

Bi + j

Cj - i

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using j - i which is off by one.

Using i + j which is not length.

The length of the substring is j - i + 1, used as the key to group palindromes by length.

5fill in blank

hard

Fill all three blanks to create a filtered map that only includes palindromes longer than 2 characters.

DSA C++

auto filteredMap = unordered_map<int, vector<string>>{};
for (const auto& [key, substrings] : palindromeMap) {
    if (key [1] 2) {
        filteredMap[[2]] = substrings;
    }
}

for (const auto& [key, val] : filteredMap) {
    cout << "Length: " << [3] << " -> " << val.size() << " substrings\n";
}

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

A>

Blength

Ckey

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of > in condition.

Using length instead of key in map assignment and print.

We filter lengths greater than 2, assign to filteredMap using key, and print key in output.

Practice

1. What is the main goal of palindrome partitioning using backtracking on a string s?

easy

A. To split s into substrings where each substring is a palindrome

B. To find the longest palindrome substring in s

C. To count the total number of palindromes in s

D. To reverse the string s using recursion

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing the string into parts where each part reads the same forwards and backwards.

2. Step 2: Role of backtracking

   Backtracking tries all possible partitions and keeps only those where every substring is a palindrome.

3. Final Answer:

   To split s into substrings where each substring is a palindrome -> Option A

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Remember: partition means split into palindrome parts [OK]

Common Mistakes:

• Confusing palindrome partitioning with finding longest palindrome
• Thinking it counts palindromes instead of partitioning
• Assuming it reverses the string

2. Which of the following is the correct base case check in a backtracking function for palindrome partitioning of string s starting at index start?

easy

A. if (start == s.length()) add current partition to result;

B. if (start > s.length()) return false;

C. if (start == s.length()) return true;

D. if (start < 0) return false;

Solution

1. Step 1: Understand base case in backtracking

   The base case occurs when the start index reaches the end of the string, meaning a full partition is formed.

2. Step 2: What to do at base case

   At this point, the current partition is a valid palindrome partition and should be added to the result list.

3. Final Answer:

   if (start == s.length()) add current partition to result; -> Option A

4. Quick Check:

   Base case adds partition when start reaches string end [OK]

Hint: Base case: start at string end means add partition [OK]

Common Mistakes:

• Returning true/false instead of adding partition
• Checking start > length instead of == length
• Using invalid index checks like start < 0

3. What is the output of the following C++ code snippet for palindrome partitioning?

void backtrack(string s, int start, vector<string>& path, vector& res) {
    if (start == s.size()) {
        res.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        string sub = s.substr(start, end - start + 1);
        string rev = sub;
        reverse(rev.begin(), rev.end());
        if (sub == rev) {
            path.push_back(sub);
            backtrack(s, end + 1, path, res);
            path.pop_back();
        }
    }
}

int main() {
    string s = "aab";
    vector res;
    vector<string> path;
    backtrack(s, 0, path, res);
    for (auto &v : res) {
        for (auto &str : v) cout << str << " ";
        cout << endl;
    }
    return 0;
}

medium

A. a a b \naab \naa b

B. a a b \naab

C. a a b \naa b

D. a a b

Solution

1. Step 1: Trace palindrome partitions of "aab"

   Possible palindrome partitions are ["a", "a", "b"] and ["aa", "b"].

2. Step 2: Check output format

   The code prints each partition on a new line with substrings separated by spaces, so output lines are "a a b" and "aa b".

3. Final Answer:

   a a b \naa b -> Option C

4. Quick Check:

   Partitions = ["a","a","b"], ["aa","b"] [OK]

Hint: List all palindrome splits, print each partition line [OK]

Common Mistakes:

• Missing the "aa" substring partition
• Printing partitions in wrong order
• Confusing substring boundaries

4. Identify the bug in this backtracking code snippet for palindrome partitioning:

void backtrack(string s, int start, vector<string>& path, vector& res) {
    if (start == s.size()) {
        res.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        string sub = s.substr(start, end - start + 1);
        if (isPalindrome(sub)) {
            path.push_back(sub);
            backtrack(s, end, path, res);  // Bug here
            path.pop_back();
        }
    }
}

medium

A. The substring extraction is incorrect

B. The recursive call should use end + 1 instead of end

C. The base case condition is wrong

D. The palindrome check function is missing

Solution

1. Step 1: Analyze recursive call index

   The recursive call uses end as the next start index, but it should move past the current substring.

2. Step 2: Correct index to avoid infinite loop

   Using end + 1 ensures the next substring starts after the current one, preventing repeated processing.

3. Final Answer:

   The recursive call should use end + 1 instead of end -> Option B

4. Quick Check:

   Next start index = end + 1 to avoid overlap [OK]

Hint: Next start index must skip current substring end [OK]

Common Mistakes:

• Using end instead of end + 1 causes infinite recursion
• Ignoring base case correctness
• Assuming substring extraction is wrong

5. Given the string s = "racecarannakayak", how many palindrome partitions can be formed using backtracking? (Assume all partitions are valid palindrome splits.)

hard

A. 5

B. 12

C. 10

D. 8

Solution

1. Step 1: Identify palindromic substrings in s

   Substrings like "racecar", "anna", "kayak" are palindromes. Smaller palindromes like "a", "c", "r" also exist.

2. Step 2: Count partitions using backtracking

   Backtracking explores all splits where each substring is palindrome. For this string, there are 8 valid partitions combining these palindromes.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   Backtracking counts 8 palindrome partitions for given string [OK]

Hint: Count all palindrome splits including big and small palindromes [OK]

Common Mistakes:

• Counting only large palindromes
• Missing smaller palindrome partitions
• Assuming fewer partitions than actual