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(string s, int start, int end) {
    while (start < end) {
        if (s[start] != s[[1]]) return false;
        start++;
        end--;
    }
    return true;
}

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

Astart

Bend - 1

Cstart + 1

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using s[start + 1] instead of s[end]

Using s[end - 1] or s[start]

To check palindrome, compare characters from start and end moving towards center. So, s[start] is compared with s[end], then end moves left by 1 (end - 1).

2fill in blank

medium

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

DSA C#

void Backtrack(string s, int start, List<string> path, List<List<string>> result) {
    if (start == s.Length) {
        result.Add(new List<string>(path));
        return;
    }
    for (int end = start; end < s.Length; end++) {
        if (IsPalindrome(s, start, end)) {
            path.[1](s.Substring(start, end - start + 1));
            Backtrack(s, end + 1, path, result);
            path.RemoveAt(path.Count - 1);
        }
    }
}

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

AAdd

BRemove

CClear

DInsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using Remove instead of Add

Using Clear which empties the list

We add the current palindrome substring to the path before exploring further.

3fill in blank

hard

Fix the error in the recursive call to continue partitioning.

DSA C#

Backtrack(s, [1], path, result);

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

Aend

Bstart + 1

Cend + 1

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using end instead of end + 1 causes infinite recursion

Using start or start + 1 is incorrect here

After choosing a palindrome substring from start to end, we move to the next index end + 1 for further partitioning.

4fill in blank

hard

Fill both blanks to complete the main function that starts backtracking.

DSA C#

List<List<string>> Partition(string s) {
    var result = new List<List<string>>();
    var path = new List<string>();
    [1](s, 0, path, result);
    return [2];
}

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

ABacktrack

BIsPalindrome

Cresult

Dpath

Attempts:

3 left

💡 Hint

Common Mistakes

Returning path instead of result

Calling IsPalindrome instead of Backtrack

We call Backtrack to start partitioning from index 0 and return the result list.

5fill in blank

hard

Fill all three blanks to complete the backtracking loop and palindrome check.

DSA C#

for (int end = [1]; end < s.Length; end++) {
    if ([2](s, start, [3])) {
        path.Add(s.Substring(start, end - start + 1));
        Backtrack(s, end + 1, path, result);
        path.RemoveAt(path.Count - 1);
    }
}

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

Astart

BIsPalindrome

Cend

Dstart + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop from 0 instead of start

Using wrong method name for palindrome check

Using wrong variable in loop condition

The loop starts from start index, checks palindrome using IsPalindrome, and uses end as loop variable.

Practice

1. What is the main goal of palindrome partitioning using backtracking?

easy

A. To find the longest palindrome substring in a string

B. To reverse the string and check if it is a palindrome

C. To split a string into all possible palindrome substrings

D. To count the number of palindromes in a string

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing a string into parts where each part is a palindrome.

2. Step 2: Role of backtracking

   Backtracking helps explore all possible ways to split the string into palindrome parts.

3. Final Answer:

   To split a string into all possible palindrome substrings -> Option C

4. Quick Check:

   Palindrome partitioning = all palindrome splits [OK]

Hint: Backtracking explores all palindrome splits of the string [OK]

Common Mistakes:

• Confusing palindrome partitioning with finding longest palindrome
• Thinking palindrome partitioning only counts palindromes
• Assuming palindrome partitioning reverses the string

2. Which of the following C# method signatures is correct for a backtracking function that partitions a string into palindromes?

easy

A. string Backtrack(string s, int start, List<string> currentPartition, List result)

B. int Backtrack(string s, int start, List<string> currentPartition)

C. bool Backtrack(string s, int start, List<string> currentPartition, List result)

D. void Backtrack(string s, int start, List<string> currentPartition, List result)

Solution

1. Step 1: Understand backtracking method requirements

   The method should explore partitions and store results, so it returns void and uses parameters to track state.

2. Step 2: Check method signatures

   void Backtrack(string s, int start, List<string> currentPartition, List result) returns void and takes parameters for string, start index, current partition, and result list, matching backtracking needs.

3. Final Answer:

   void Backtrack(string s, int start, List<string> currentPartition, List result) -> Option D

4. Quick Check:

   Backtracking method returns void with state parameters [OK]

Hint: Backtracking methods usually return void and use parameters to track state [OK]

Common Mistakes:

• Using return types other than void for backtracking
• Missing the result list parameter to store partitions
• Confusing return type with boolean or string

3. What will be the output of the following C# code snippet?

var result = new List();
Backtrack("aab", 0, new List<string>(), result);
Console.WriteLine(result.Count);

Assuming Backtrack partitions the string into all palindrome substrings correctly.

medium

A. 2

B. 3

C. 1

D. 4

Solution

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

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

2. Step 2: Count all palindrome partitions

   There are 2 partitions, so result.Count will be 2 after backtracking.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Palindrome partitions of "aab" = 2 [OK]

Hint: Count all palindrome partitions generated by backtracking [OK]

Common Mistakes:

• Counting substrings instead of partitions
• Forgetting "aa" is a palindrome
• Assuming single partition only

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

void Backtrack(string s, int start, List<string> current, List result) {
  if (start == s.Length) {
    result.Add(new List<string>(current));
    return;
  }
  for (int end = start; end < s.Length; end++) {
    if (IsPalindrome(s, start, end)) {
      current.Add(s.Substring(start, end - start));
      Backtrack(s, end + 1, current, result);
      current.RemoveAt(current.Count - 1);
    }
  }
}

medium

A. Base case condition should be start > s.Length

B. Substring length calculation is incorrect

C. RemoveAt should remove from index 0

D. IsPalindrome method parameters are wrong

Solution

1. Step 1: Check substring length calculation

   Substring(start, length) needs length = end - start + 1, but code uses end - start, missing last character.

2. Step 2: Verify other parts

   IsPalindrome parameters and RemoveAt usage are correct; base case is correct as start == s.Length.

3. Final Answer:

   Substring length calculation is incorrect -> Option B

4. Quick Check:

   Substring length = end - start + 1 [OK]

Hint: Substring length must include end index +1 [OK]

Common Mistakes:

• Using substring length as end - start instead of end - start + 1
• Removing wrong index from current list
• Incorrect base case condition

5. Given the string "racecar", how many palindrome partitions will the backtracking algorithm find? Consider all possible partitions where each substring is a palindrome.

hard

A. 10

B. 6

C. 8

D. 4

Solution

1. Step 1: List all palindrome partitions of "racecar"

   Partitions include ["r", "a", "c", "e", "c", "a", "r"], ["r", "a", "cec", "a", "r"], ["r", "aceca", "r"], ["racecar"], and others.

2. Step 2: Count all valid palindrome partitions

   Counting carefully, there are 10 valid palindrome partitions in total.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Palindrome partitions of "racecar" = 10 [OK]

Hint: Count all palindrome splits including nested palindromes [OK]

Common Mistakes:

• Counting only single character partitions
• Missing longer palindrome substrings like "cec" or "aceca"
• Assuming only 1 or 2 partitions