LeetCode #5: Longest Palindromic Substring

Find the longest substring that reads the same forwards and backwards using the "expand around center" technique.

Difficulty: MediumPattern: Two Pointers, StringTime: 8 min read

What is a Palindrome?

A palindrome is a word, phrase, or sequence that reads the same forwards and backwards.

✅ Valid:

racecar
madam
12321
a

❌ Not Palindromes:

hello
abc
race

In this problem, we’re looking for the longest palindromic substring — not necessarily the whole string.

The Problem

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

Examples

Input: "babad" → Output: "bab" (Both 'bab' and 'aba' are valid)

Input: "cbbd" → Output: "bb" (Longest palindromic substring)

Input: "racecar" → Output: "racecar" (The whole string is a palindrome)

Input: "a" → Output: "a" (Single character is always a palindrome)

❌ Brute Force: Check All Substrings

Generate every possible substring and check if it is a palindrome.

function longestPalindrome(s) {
  let longest = "";

  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const substr = s.slice(i, j + 1);
      if (isPalindrome(substr) && substr.length > longest.length) {
        longest = substr;
      }
    }
  }

  return longest;
}

function isPalindrome(str) {
  let left = 0, right = str.length - 1;
  while (left < right) {
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }
  return true;
}

❌ O(n³) time — too slow for long strings!

✅ Optimized: Expand Around Center

Instead of checking all substrings, we treat every index as a potential center of a palindrome.

Key Insight

Every palindrome has a center:

Odd-length: One character center (e.g. "racecar" → 'e')
Even-length: Between two characters (e.g. "abba" → between 'b' and 'b')

So we try 2n - 1 centers (n characters + n-1 gaps).

How It Works

Loop through each character in the string
For each, expand outwards as long as characters match
Do this for both odd (same center) and even (between two) cases
Track the longest palindrome found

function longestPalindrome(s) {
  if (s.length < 2) return s;

  let start = 0;
  let maxLength = 1;

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      const len = right - left + 1;
      if (len > maxLength) {
        maxLength = len;
        start = left;
      }
      left--;
      right++;
    }
  }

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

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

Time Complexity: O(n²) — much better than O(n³).
Space: O(1) — no extra data structures.

🌍 Real-World Applications

Palindrome detection isn’t just a puzzle; it appears in biology, security, and data validation.

Bioinformatics: DNA Sequences

Some DNA sequences are palindromic and play a role in gene regulation. Tools scan genetic data for palindromes to identify functional regions.

Cybersecurity: Obfuscation Detection

Malware sometimes uses palindromic strings to evade signature detection. Security scanners look for unusual symmetric patterns.

Search & Autocomplete

Search engines may highlight or prioritize palindromic queries (e.g., "racecar") for fun or branding (like Google‘s palindrome doodles).

Game Development

Word games (Scrabble, Wordle) often include palindrome challenges. This algorithm helps generate or validate them.

Why This Matters: This problem teaches how to leverage symmetry and reduce search space; a key idea in algorithm design.

Summary

The "expand around center" technique turns a cubic problem into a quadratic one — and it is intuitive: treat every character (and gap) as a potential palindrome center.

This pattern is a gateway to even faster algorithms like Manacher‘s Algorithm (O(n))

View All Challenges