longest-palindromic-substring.ts

/**
 * 5. Longest Palindromic Substring  (Medium)
 * Link: https://leetcode.com/problems/longest-palindromic-substring/
 *
 * Return the longest contiguous substring of `s` that is a palindrome.
 *
 * Example:
 *   Input:  s = "babad"
 *   Output: "bab"        // "aba" is also a valid answer
 *
 * Approach:
 *   Expand around center. Every palindrome has a center — either a single
 *   character (odd length) or a gap between two characters (even length). Try all
 *   2n-1 centers, expanding outward while the characters match, and keep the
 *   longest span found.
 *
 * Time:  O(n^2)
 * Space: O(1)
 */
export function longestPalindrome(s: string): string {
  if (s.length < 2) return s;

  let start = 0;
  let maxLen = 1;

  const expand = (left: number, right: number): void => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > maxLen) {
        start = left;
        maxLen = right - left + 1;
      }
      left--;
      right++;
    }
  };

  for (let i = 0; i < s.length; i++) {
    expand(i, i); // odd-length center
    expand(i, i + 1); // even-length center
  }

  return s.slice(start, start + maxLen);
}