Longest Palindromic Substring

MediumStrings

Return the longest contiguous substring of s that reads the same forwards and backwards.

Constraints

1 <= s.length <= 1000
s consists of digits and English letters

Expand around center

Time O(n^2)Space O(1)

Every palindrome has a center, either a character (odd length) or a gap between two characters (even length). Expand outward from each of the 2n-1 centers and keep the longest match.

#include <bits/stdc++.h>
using namespace std;

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int start = 0, maxLen = 1;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
        if (r - l - 1 > maxLen) { maxLen = r - l - 1; start = l + 1; }
    };
    for (int i = 0; i < (int)s.size(); i++) {
        expand(i, i);
        expand(i, i + 1);
    }
    return s.substr(start, maxLen);
}