Longest Palindrome Within a String

medium strings palindrome

Problem

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

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);
}

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