Longest Palindromic Substring in DSA C - Time & Space Complexity

Time Complexity: Longest Palindromic Substring

O(n²)

Understanding Time Complexity

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

How does the number of steps grow when the string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int expandAroundCenter(char *s, int left, int right, int n) {
    int L = left, R = right;
    while (L >= 0 && R < n && s[L] == s[R]) {
        L--;
        R++;
    }
    return R - L - 1;
}

char* longestPalindrome(char * s) {
    int start = 0, end = 0;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        int len1 = expandAroundCenter(s, i, i, len);
        int len2 = expandAroundCenter(s, i, i + 1, len);
        int maxLen = (len1 > len2) ? len1 : len2;
        if (maxLen > end - start) {
            start = i - (maxLen - 1) / 2;
            end = i + maxLen / 2;
        }
    }
    s[end + 1] = '\0';
    return s + start;
}
    

This code finds the longest palindromic substring by expanding around each character and its neighbor.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop inside expandAroundCenter that expands outwards checking characters.
• How many times: For each character in the string (n times), we call this expansion twice, 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 done.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the input size.

Common Mistake

[X] Wrong: "The expansion around center runs in linear time overall because it stops early."

[OK] Correct: While each expansion stops early for many centers, in the worst case (like a string of identical characters), expansions can reach the full length, making total work quadratic.

Interview Connect

Understanding this time complexity helps you explain why this approach is efficient enough for many cases and when to consider faster algorithms.

Self-Check

"What if we used dynamic programming to store palindrome checks instead of expanding around centers? How would the time complexity change?"