Longest Palindromic Substring in DSA Python - Time & Space Complexity

Time Complexity: Longest Palindromic Substring

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find the longest palindromic substring changes as the input string gets longer.

Specifically, how does the number of steps grow when checking all possible palindromes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def longest_palindrome(s: str) -> str:
    start, max_len = 0, 1
    for i in range(len(s)):
        # Check odd length palindrome
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
        # Check even length palindrome
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
    return s[start:start + max_len]

This code checks all possible centers of palindromes and expands outwards to find the longest palindrome substring.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Expanding around each center to check palindrome substrings.
• How many times: For each character (n times), two expansions happen (odd and even length), each expanding up to n steps in worst case.

How Execution Grows With Input

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

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

Pattern observation: Doubling the input size roughly quadruples the work, showing a square growth pattern.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the input length, so longer strings take much more time.

Common Mistake

[X] Wrong: "Since we only check around each character, the time is O(n)."

[OK] Correct: Each center can expand up to n steps, so the total checks add up to about n times n, not just n.

Interview Connect

Understanding this time complexity helps you explain why some palindrome solutions are slower and shows your grasp of nested loops and their costs.

Self-Check

"What if we used dynamic programming to store palindrome results? How would the time complexity change?"