Palindrome Partitioning Using Backtracking in DSA Typescript - 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.

Specifically, how does the backtracking process scale with the size of the string?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isPalindrome(s: string, start: number, end: number): boolean {
  while (start < end) {
    if (s.charAt(start) !== s.charAt(end)) return false;
    start++;
    end--;
  }
  return true;
}

function backtrack(s: string, start: number, path: string[], result: string[][]): void {
  if (start === s.length) {
    result.push([...path]);
    return;
  }
  for (let end = start; end < s.length; end++) {
    if (isPalindrome(s, start, end)) {
      path.push(s.substring(start, end + 1));
      backtrack(s, end + 1, path, result);
      path.pop();
    }
  }
}
    

This code finds all ways to split a string into palindrome parts using backtracking.

Identify Repeating Operations

• 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 possible palindrome partitions grows very fast.

Input Size (n)	Approx. Operations
3	~5 to 10 checks and recursive calls
10	Hundreds of palindrome checks and recursive calls
15	Thousands to tens of thousands of operations

Pattern observation: The operations grow exponentially because each character can start a new palindrome or extend one, creating many combinations.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time needed grows very fast, roughly doubling with each added character, multiplied by the cost to check palindromes.

Common Mistake

[X] Wrong: "The time complexity is just O(n^2) because of the nested loops."

[OK] Correct: The recursion explores many partitions, which leads to exponential growth, not just quadratic.

Interview Connect

Understanding this complexity helps you explain how backtracking explores many possibilities and why pruning or memoization might be needed.

Self-Check

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