Palindrome Partitioning DP Minimum Cuts in DSA Typescript - Time & Space Complexity

Time Complexity: Palindrome Partitioning DP Minimum Cuts

O(n²)

Understanding Time Complexity

We want to know how the time needed to find the minimum cuts for palindrome partitioning changes as the input string gets longer.

Specifically, how the number of steps grows when checking all possible partitions and palindromes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function minCut(s: string): number {
  const n = s.length;
  const dp = new Array(n).fill(0);
  const palindrome = Array.from({ length: n }, () => new Array(n).fill(false));

  for (let end = 0; end < n; end++) {
    let minCuts = end;
    for (let start = 0; start <= end; start++) {
      if (s[start] === s[end] && (end - start < 2 || palindrome[start + 1][end - 1])) {
        palindrome[start][end] = true;
        minCuts = start === 0 ? 0 : Math.min(minCuts, dp[start - 1] + 1);
      }
    }
    dp[end] = minCuts;
  }
  return dp[n - 1];
}
    

This code finds the minimum number of cuts needed to split a string into palindromes using dynamic programming.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops checking all substring pairs (start, end) and palindrome checks.
• How many times: Outer loop runs n times; inner loop runs up to n times for each outer loop, totaling about n×n = n² times.

How Execution Grows With Input

As the string length grows, the number of substring checks grows roughly with the square of the length.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The work grows roughly by the square of the input size, so doubling the input makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the string length, because we check all substring pairs.

Common Mistake

[X] Wrong: "Since we only loop once over the string, the time is O(n)."

[OK] Correct: We actually have a nested loop checking all substrings, so the time grows much faster than just one pass.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming reduces repeated work when checking palindromes, a common pattern in coding challenges.

Self-Check

"What if we used a simple recursive approach without memoization? How would the time complexity change?"