// Longest Palindromic Substring

task

Given a string s, return the longest substring that is a palindrome. If more than one has the maximal length, any one of them is accepted.

s = "abccbaby"  →  "abccba"   (length 6; "bab" also occurs, but shorter)

how to think

Checking every substring for palindrome-ness is O(n³) — O(n²) substrings, O(n) each to verify. A DP table over (i, j) pairs (see dynamic programming) gets you to O(n²) time but pays O(n²) space for the table. There’s a cheaper route: every palindrome has exactly one center — either a single character (odd length, like "aba") or the gap between two characters (even length, like "abba"). A string of length n has 2n - 1 such centers. Try every one, expand outward while the two sides still mirror each other, and track the widest expansion you find. That’s O(n²) time, O(1) extra space, no table.

The expansion step is exactly the third two-pointer shape — start together (or one apart) and walk outward — just called once per center instead of once for the whole problem.

solution

public string LongestPalindrome(string s)
{
    if (s.Length < 1) return "";
    int start = 0, maxLen = 1;

    for (int center = 0; center < s.Length; center++)
    {
        int len1 = ExpandAroundCenter(s, center, center);       // odd length, single center
        int len2 = ExpandAroundCenter(s, center, center + 1);   // even length, gap center
        int len = Math.Max(len1, len2);
        if (len > maxLen)
        {
            maxLen = len;
            start = center - (len - 1) / 2;
        }
    }
    return s.Substring(start, maxLen);
}

private int ExpandAroundCenter(string s, int left, int right)
{
    while (left >= 0 && right < s.Length && s[left] == s[right])
    {
        left--;
        right++;
    }
    return right - left - 1;
}

trace

s = "abccbaby" (index: a0 b1 c2 c3 b4 a5 b6 y7), starting maxLen = 1:

Center 2 — the gap between the two cs expands the whole way out to the ends:

Final answer — six characters win, the trailing "by" never gets folded in:

At center 5 ('a'), the odd expansion separately finds "bab" (length 3) — a real palindrome, just not the longest one, so it never overwrites the length-6 answer already on record.

why it works

Every palindrome, of any length, has exactly one center: a single index for odd lengths, a gap for even ones. So the longest palindrome in s must be found by some center in the 2n - 1 we try — there’s nowhere else it could be centered. For a fixed center, expanding outward is monotonic: once s[left] != s[right], no larger radius from that same center can ever become valid again, because the mismatched pair is still inside any wider window. That’s what makes “expand until the first mismatch, then stop” correct rather than just convenient.

common bugs

• Checking only odd-length centers — misses even-length answers entirely, like "bb" in "cbbd".
• Reconstructing the start index as center - len / 2 instead of center - (len - 1) / 2 — the off-by-one only shows up on even-length matches. For odd lengths integer division makes the two expressions coincide, so a test suite skewed toward odd palindromes won’t catch it.
• Forgetting s.Substring’s second argument is a length, not an end index — a habit carried over from languages that slice by [start, end).
• Skipping the s.Length < 1 guard — an empty string with maxLen defaulted to 1 would throw on s.Substring(0, 1).
• Assuming there’s a single “correct” answer to test against — inputs like "babad" have multiple valid longest palindromes ("bab" and "aba" are both length 3); hardcode the length, not the exact string, when writing your own test cases.

variants you can now solve

• Valid Palindrome (LC 125) — mirror-compare one fixed string instead of searching every possible center for the best one.
• Palindromic Substrings (LC 647) — same expand-from-center engine; instead of tracking the longest, increment a counter on every successful expansion (every radius, not just the final one, is itself a valid palindrome).
• Longest Palindromic Subsequence (LC 516) — sounds similar, but subsequence (not substring) breaks the “one center, expand outward” argument entirely; that one needs real DP.