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 finds all palindrome partitions of the string "aab"?

DSA C#

using System;
using System.Collections.Generic;

class Solution {
    public IList<IList<string>> Partition(string s) {
        var result = new List<IList<string>>();
        Backtrack(s, 0, new List<string>(), result);
        return result;
    }

    private void Backtrack(string s, int start, List<string> current, IList<IList<string>> 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 + 1));
                Backtrack(s, end + 1, current, result);
                current.RemoveAt(current.Count - 1);
            }
        }
    }

    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

class Program {
    static void Main() {
        var sol = new Solution();
        var partitions = sol.Partition("aab");
        foreach (var partition in partitions) {
            Console.WriteLine(string.Join(",", partition));
        }
    }
}

A [["a","a","b"]]

B [["a","ab"],["aa","b"]]

C [["a","a","b"],["aa","b"]]

D [["aa","b"],["a","b"]]

💡 Hint

Check all substrings and verify if they are palindromes before adding to the partition.

The code finds all partitions where each substring is a palindrome. For "aab", the partitions are ["a","a","b"] and ["aa","b"].

🧠 Conceptual

intermediate

Number of Palindrome Partitions for "racecar"

How many palindrome partitions does the string "racecar" have using backtracking?

A 4

B 6

C 10

D 8

💡 Hint

Consider all possible palindrome substrings and count partitions.

The string "racecar" has 4 palindrome partitions when all possible palindrome substrings are considered.

🔧 Debug

advanced

Identify the Error in Palindrome Partitioning Code

What error will the following code produce when run for palindrome partitioning?

DSA C#

public void Backtrack(string s, int start, List<string> current, IList<IList<string>> 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 + 1));
            Backtrack(s, end + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

private bool IsPalindrome(string s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

A StackOverflowException

B ArgumentOutOfRangeException

C No error, runs correctly

D IndexOutOfRangeException

💡 Hint

Check the base case condition for the recursion.

The base case uses 'start > s.Length' which allows start == s.Length + 1 causing substring calls to go out of range.

🚀 Application

advanced

Find the Longest Palindromic Partition

Given the string "banana", which palindrome partition has the longest single palindrome substring?

A ["b", "anana"]

B ["b", "ana", "n", "a"]

C ["b", "a", "n", "a", "n", "a"]

D ["banan", "a"]

💡 Hint

Look for the longest palindrome substring inside the partitions.

"anana" is the longest palindrome substring in "banana", so the partition ["b", "anana"] contains the longest palindrome.

❓ Predict Output

expert

Output of Palindrome Partitioning for "abc"

What is the output of the following C# palindrome partitioning code for the input string "abc"?

DSA C#

using System;
using System.Collections.Generic;

class Solution {
    public IList<IList<string>> Partition(string s) {
        var result = new List<IList<string>>();
        Backtrack(s, 0, new List<string>(), result);
        return result;
    }

    private void Backtrack(string s, int start, List<string> current, IList<IList<string>> 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 + 1));
                Backtrack(s, end + 1, current, result);
                current.RemoveAt(current.Count - 1);
            }
        }
    }

    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

class Program {
    static void Main() {
        var sol = new Solution();
        var partitions = sol.Partition("abc");
        foreach (var partition in partitions) {
            Console.WriteLine(string.Join(",", partition));
        }
    }
}

A [["abc"]]

B [["a","b","c"]]

C [["a","bc"],["ab","c"]]

D [["a","b"],["c"]]

💡 Hint

Check which substrings are palindromes in "abc".

Only single characters are palindromes in "abc", so the only partition is ["a","b","c"].

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