Palindrome Partitioning Using Backtracking in DSA C# - Time & Space Complexity

Time Complexity: Palindrome Partitioning Using Backtracking

O(n * 2^n)

Understanding Time Complexity

We want to understand how the time needed to find all palindrome partitions grows as the input string gets longer.

How does the number of steps change when we try all possible palindrome splits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void Backtrack(string s, int start, List<string> current, List<List<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;
    }
    return true;
}
    

This code finds all ways to split a string into parts where each part is a palindrome, using backtracking.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop tries every possible substring start to end, and the recursive calls explore all partitions.
• How many times: The recursion explores many combinations, and palindrome checks happen for each substring considered.

How Execution Grows With Input

As the string length grows, the number of palindrome partitions grows very fast because many substring combinations are possible.

Input Size (n)	Approx. Operations
10	Thousands of checks and recursive calls
100	Millions to billions of operations
1000	Extremely large, often impractical without optimization

Pattern observation: The number of operations grows faster than any simple polynomial, roughly exponential with input size.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time grows very fast as the string gets longer, because we try many partitions and check palindromes for each.

Common Mistake

[X] Wrong: "The algorithm runs in polynomial time because it just loops over the string."

[OK] Correct: The algorithm explores all possible partitions, which grow exponentially, not just a simple loop.

Interview Connect

Understanding this complexity helps you explain why backtracking can be slow and when to expect exponential time, a key skill in interviews.

Self-Check

"What if we cached palindrome checks to avoid repeating them? How would the time complexity change?"

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