Longest Palindromic Substring

medium strings palindrome

Problem

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

Inputs = "babad"

Output"bab" or "aba"

Every palindrome has either an odd centre (one character) or an even centre (between two characters). Try all 2n − 1 centres and expand while characters match.

def longest_palindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return l + 1, r - 1
    best = (0, -1)
    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > best[1] - best[0]:
                best = (l, r)
    return s[best[0]:best[1] + 1]

function longestPalindrome(s) {
  let bestL = 0, bestR = -1;
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return [l + 1, r - 1];
  };
  for (let i = 0; i < s.length; i++) {
    for (const [l, r] of [expand(i, i), expand(i, i + 1)]) {
      if (r - l > bestR - bestL) { bestL = l; bestR = r; }
    }
  }
  return s.slice(bestL, bestR + 1);
}

class Solution {
    int bestL = 0, bestR = 0;
    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return s.substring(bestL, bestR + 1);
    }
    private void expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
        l++; r--;
        if (r - l > bestR - bestL) { bestL = l; bestR = r; }
    }
}

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

Explanation

Every palindrome has a center and is symmetric around it. So instead of testing every possible substring, we pick each center and grow outward as long as the characters on both sides keep matching.

There is one catch: palindromes can be odd-length (centered on a single character, like "aba") or even-length (centered between two characters, like "abba"). So at each index i we run the expansion twice: once with expand(i, i) and once with expand(i, i+1).

The helper walks a left pointer l down and a right pointer r up while s[l] == s[r]. When they stop matching it backs off by one and returns the valid range. Whenever a range is longer than our best so far, we remember it.

This works because any palindrome, no matter how long, can be discovered by starting from its middle and stepping outward, so trying all 2n-1 centers is guaranteed to find the longest one.

Example: for "babad", expanding around the center a at index 1 grows to "bab", length 3, which beats the single-letter starts and becomes the answer.

Time: O(n²) Space: O(1)