Longest Palindromic Substring

📌 Definition:

Find the longest contiguous substring that is a palindrome (e.g. "babad" -> "bab" or "aba").

📖 Detailed Explanation:

Expand around each center: every index (and every gap between indices, for even-length palindromes) is a potential center; grow outward while characters match and track the longest span. This is O(n^2) time, O(1) space — simpler than the O(n) Manacher's algorithm and usually sufficient.

💻 Solutions:

public static String longestPalindrome(String s) {
    if (s.isEmpty()) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}
private static int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

function longestPalindrome(s) {
  if (!s) return '';
  let start = 0, end = 0;
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return r - l - 1;
  };
  for (let i = 0; i < s.length; i++) {
    const len = Math.max(expand(i, i), expand(i, i + 1));
    if (len > end - start) {
      start = i - ((len - 1) >> 1);
      end = i + (len >> 1);
    }
  }
  return s.slice(start, end + 1);
}

def longest_palindrome(s):
    if not s:
        return ''
    start = end = 0

    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return r - l - 1

    for i in range(len(s)):
        length = max(expand(i, i), expand(i, i + 1))
        if length > end - start:
            start = i - (length - 1) // 2
            end = i + length // 2
    return s[start:end + 1]

🔑 Key Points:

Expand around 2n-1 centers (odd and even)
Grow while both ends match
Track the longest span seen
O(n^2) time, O(1) space

🌍 Real-World Example:

Palindromic-span detection appears in bioinformatics (finding symmetric DNA motifs) and text analysis; the expand-around-center idea is broadly reusable.

🎯 Scenario-Based Interview Question:

A candidate only checks odd-length palindromes and misses "abba". What is missing?

‹ Previous

Check if a String is a Pangram

Next ›

Trapping Rain Water