Finding Palindromic Substrings — Part 1: O(n³) and O(n²) Solutions

What is a Palindrome?

A string that reads the same backward is a palindrome.

What is a Palindromic Substring?

Any continuous part (substring) inside a string that is itself a palindrome is a palindromic substring.

Take s = "abaab":

index:  0  1  2  3  4
char:   a  b  a  a  b

Let's look at some of its substrings:

Notice: "aba" and "aa" — these two are non-trivial palindromic substrings (length > 1).

The Problem

You are given a string s (of length n). Find the longest palindromic substring, or count all palindromic substrings.

We'll look at 3 approaches to solve this:

Approach 1: Brute Force — O(n³)

The Idea

The most straightforward thought:

1. Enumerate every possible substring → O(n²) pairs (i, j)
2. Check whether each substring is a palindrome → O(n) time

Total: O(n²) × O(n) = O(n³)

How to check a palindrome?

To check whether a string is a palindrome, move inward from both the start and the end at the same time, comparing each pair:

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

For "abba":

• s[0]='a' vs s[3]='a' → match
• s[1]='b' vs s[2]='b' → match
• → Palindrome!

The full O(n³) code

string longestPalindrome(string s) {
    int n = s.size();
    string result = "";

    for (int i = 0; i < n; i++) {           // start position
        for (int j = i; j < n; j++) {        // end position
            if (isPalindrome(s, i, j)) {     // O(n) check
                if (j - i + 1 > result.size()) {
                    result = s.substr(i, j - i + 1);
                }
            }
        }
    }
    return result;
}

Why O(n³)?

• The two outer loops → enumerate every substring → O(n²)
• For each one, isPalindrome() → worst case O(n)
• Total: n² × n = n³

What's the problem?

When n = 1000: 1000³ = 10⁹ operations — TLE (Time Limit Exceeded) on most online judges!

We need something better.

Approach 2: Center Expansion — O(n²)

The core idea

In brute force we check every substring. But thinking a bit differently — every palindrome has a center. Expanding outward from the center gives you the palindrome.

Two kinds of center

A palindrome can be of two kinds:

1. Odd-length — the center is a single character:

  "a b a"
      ↑
   center = 'b'

2. Even-length — the center is the gap between two characters:

  "a b b a"
      ↑ ↑
   center = between 'b' and 'b'

How to expand from the center?

Say center = position i. Move out on both sides at the same time:

• s[i-1] == s[i+1]? → if yes, the palindrome is growing, keep expanding
• if no, stop

s = "abacaba", center = 3 (c):

Step 0:  _ _ _ c _ _ _    → "c" (length 1)
Step 1:  _ _ a c a _ _    → s[2]='a' == s[4]='a' ✓ → "aca" (length 3)
Step 2:  _ b a c a b _    → s[1]='b' == s[5]='b' ✓ → "bacab" (length 5)
Step 3:  a b a c a b a    → s[0]='a' == s[6]='a' ✓ → "abacaba" (length 7)
Step 4:  boundary reached, stop

For even-length

s = "abba", center = between index 1 and 2:

Step 0:  _ b b _          → s[1]='b' == s[2]='b' ✓ → "bb" (length 2)
Step 1:  a b b a          → s[0]='a' == s[3]='a' ✓ → "abba" (length 4)
Step 2:  boundary reached, stop

The full O(n²) code

// expands from the center in both directions and returns the palindrome's length
int expandFromCenter(string &s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;  // palindrome length
}

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int start = 0, maxLen = 1;

    for (int i = 0; i < n; i++) {
        // Odd-length: center = i
        int len1 = expandFromCenter(s, i, i);

        // Even-length: center = between i and i+1
        int len2 = expandFromCenter(s, i, i + 1);

        int len = max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substr(start, maxLen);
}

Why O(n²)?

• Outer loop: n centers → O(n)
• Expansion from each center: worst case O(n) (for example in "aaaaaaa" each center expands all the way to the full string)
• Total: n × n = n²

O(n³) vs O(n²) comparison

What's the problem?

When n = 100,000 or more, even O(n²) isn't enough. For that you need Manacher's Algorithm — O(n)!

Why is Center Expansion better than Brute Force?

In brute force we do a lot of redundant work. Say s[2..5] is a palindrome — then s[3..4] is also a palindrome, but brute force checks it all over again!

Center expansion avoids this redundancy — once you fix a center, expanding from the inside out covers all the nested palindromes automatically.

But center expansion has redundancy too — we don't reuse information about the smaller palindromes sitting inside a larger one.

Say "abacaba" — expanding from center 3 (c) we learn the whole string is a palindrome. Now when we go to center 5 (a), we expand from scratch again! But center 5 sits inside the palindrome of center 3 — a palindrome is symmetric, so the surroundings of center 5 are exactly the same as those of center 1! Reusing this information lets us skip a lot of expansion.

Manacher's Algorithm does exactly this — it uses the mirror property to reuse information from palindromes found earlier, and so it drops down to O(n).

Where we are so far

In Part 1 we learned what a palindrome is, the O(n³) brute force, and the O(n²) center expansion. In Part 2 we'll see how to remove the redundancy in center expansion and reach O(n).

Read Part 2: Manacher's Algorithm — O(n) Solution