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 the string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code finds all ways to split a string into palindrome parts 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 call explores partitions from there.
• How many times: The recursion explores all possible partitions, which can be very large, and each palindrome check scans part of the substring.

How Execution Grows With Input

As the string length grows, the number of possible partitions grows very fast, and each partition requires palindrome checks.

Input Size (n)	Approx. Operations
10	Thousands of checks and recursive calls
100	Millions to billions of operations
1000	Operations grow beyond practical limits

Pattern observation: The number of partitions grows exponentially, so the time grows very quickly as n increases.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time needed grows roughly like 2 to the power of the string length times the length itself, because we explore many partitions and check palindromes.

Common Mistake

[X] Wrong: "The algorithm runs in polynomial time because it just uses loops and recursion."

[OK] Correct: The number of possible palindrome partitions grows exponentially, so the recursion explores an exponential number of cases, not just polynomial.

Interview Connect

Understanding this complexity helps you explain why backtracking can be slow and when to expect exponential time, which is a valuable skill in problem solving.

Self-Check

"What if we used memoization to store palindrome checks? How would the time complexity change?"

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