Longest Palindromic Substring

Practice Link

Given a string s, return the longest palindromic substring in s.

Implementation#

Brute Force#

Generate every possible substring using two nested loops [i..j], then for each substring check character by character whether it is a palindrome. Track the longest one found. Three nested levels of work give O(n³) — too slow for large strings.

• Find all possible substrings
• Check for each substring to be a palindrome

Time Complexity - O(n^3)

• O(n^2) -> find substrings
• O(n) -> check palindrome

Space Complexity - O(1)

Better Approach#

• Instead of finding the palindrome from start idx, its better to find the center of the susbtsring and expand to check for palindrome.

class Solution {
public:
    string res = "";
    int resLen = 0;
    void findPalindrome(int l, int r, string s)
    {
        while(l >= 0 && r < s.length() && s[l]==s[r])
        {
            int currLen = r-l+1;
            if(currLen > resLen)
            {
                res = s.substr(l, r-l+1);
                resLen = currLen;
            }
            l--;
            r++;
        }
    }
    string longestPalindrome(string s) {
        

        for(int i=0;i<s.length();i++)
        {
            // For odd length
            findPalindrome(i, i, s);

            // For even length
            findPalindrome(i, i+1, s);

        }
        return res;
    }
};

Time Complexity: O(n^2), For every char we are expanding and checking for plaindrome.

Space Coomplexity: O(1)

Dynamic Programming Approach#

Build a 2D boolean table dp[i][j] where true means s[i..j] is a palindrome. Fill it bottom-up by length: all single characters are palindromes (dp[i][i] = true); adjacent equal characters form length-2 palindromes; for lengths ≥ 3, dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]. Track the starting index and max length of the longest palindrome found. This is the same O(n²) time as expand-around-center but uses O(n²) space to explicitly cache every subproblem.

• Useful when you want to track all palindromic substrings, not just the longest one -> can store all the palindromes.
• Explicitly stores subproblem solutions
• But O(n^2) space → heavy on memory

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if(n==0)
            return "";

        vector<vector<bool>> dp(n , vector<bool> (n, false));
        int maxLen = 1;
        int start = 0;

        // For substring of length 1
        for(int i=0;i<n;i++)
            dp[i][i] = true;

        // For substring of length 2
        for(int i=0;i<n-1;i++){
            if(s[i]==s[i+1]){
                dp[i][i+1] = true;
                start = i;
                maxLen = 2;
            }
        }

        // For substring of length >= 3
        for(int len = 3;len<=n;len++)
        {
            for(int i=0;i<=n-len;i++)
            {
                int j = i + len -1;
                
                if(s[i]==s[j] && dp[i+1][j-1])
                {
                    dp[i][j] = true;
                    start = i;
                    maxLen = len;
                }
            }
        }
        
        return s.substr(start, maxLen);
    }
};

Time Complexity: O(n^2), For every char we are expanding and checking for plaindrome.

Space Coomplexity: O(n^2)

Comparison#

Follow Up#

What happens to the performance if the input string consists of 1000 identical characters? Could we skip redundant checks?#

With a string like "aaaa...a" (n identical characters), every single substring is a palindrome. Both expand-around-center and DP still run at O(n²) — they faithfully expand from all n centers and fill the full DP table — but all that work produces the same answer: the entire string. The algorithms don't know this upfront, so no work is skipped.

Why redundant checks pile up:

In expand-around-center, the center at index i expands out to radius i (or n-1-i). Each expansion checks s[l] == s[r], which is always true. So every expansion runs to completion — roughly n²/4 total character comparisons just to confirm what's already obvious.

Can we skip them?

Yes — with a small preprocessing step using Manacher's Algorithm. The key insight is that palindromes can be mirrored across a previously found palindrome's center. If we're expanding from center i and we know the palindrome radius p[mirror] for a symmetric center mirror, we can initialize p[i] = min(p[mirror], reach - i) instead of starting from zero. This reuses already-computed radii and avoids re-checking characters we've already verified.

For "aaaa...a", Manacher fills the radius array [0, 1, 2, ..., n/2, ..., 2, 1, 0] in O(n) total — the right boundary keeps advancing without ever retreating, so each character position is processed at most twice.

Manacher's Algorithm (O(n) time, O(n) space):

string longestPalindrome(string s) {
    // Transform: "abc" -> "#a#b#c#"  (handles even/odd uniformly)
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = t.size();

    vector<int> p(n, 0);   // p[i] = palindrome radius at i in transformed string
    int center = 0, right = 0;

    for (int i = 0; i < n; i++) {
        int mirror = 2 * center - i;
        if (i < right)
            p[i] = min(right - i, p[mirror]);  // reuse mirror's radius

        // Expand beyond the known boundary
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0
               && t[i + p[i] + 1] == t[i - p[i] - 1])
            p[i]++;

        // Update center and right boundary
        if (i + p[i] > right) {
            center = i;
            right  = i + p[i];
        }
    }

    // Find the index with the largest radius
    int maxR = 0, bestCenter = 0;
    for (int i = 0; i < n; i++)
        if (p[i] > maxR) { maxR = p[i]; bestCenter = i; }

    int start = (bestCenter - maxR) / 2;   // map back to original string
    return s.substr(start, maxR);
}

For "aaaa...a" (n = 1000): Manacher processes each transformed character exactly once — the right pointer only moves forward — giving O(n) time vs O(n²) for expand-around-center. The redundant re-checks are eliminated entirely via the mirror property.