Longest Palindromic Substring

This one looks scary at first. So many interview lists put it in the “hard” pile. But once you see the center trick it becomes easy. The whole game here is to stop checking every possible piece of the string. We pick smart starting points instead.

🎯 The Problem

You get a string. You must find its longest palindrome piece. A palindrome is text that reads the same both ways, like “level” or “aba”.

The rules:

• Find the longest part that reads the same forwards and backwards.
• The answer must be one continuous piece. You cannot skip letters in the middle.
• A single letter counts as a palindrome of length one.
• If two pieces tie for longest, either one is correct.

For "babad", both "bab" and "aba" work. They are length three.

Input:  s = "babad"
Output: "bab"

Explanation: "bab" reads the same forwards and backwards.
             "aba" is also a valid answer of the same length.

Here is the problem drawn out. We are scanning the string for the widest mirror-like piece.

🐢 Approach 1: Check Every Piece (Brute Force)

The idea in one line: try every possible piece and test if it is a palindrome.

The idea:

• Pick a start index. Pick an end index. That gives one piece.
• Walk that piece from both ends. Check every letter matches.
• Keep the longest piece that passes.

How it works:

• Two nested loops pick the start and the end.
• A third walk checks if that piece reads the same both ways.

Why it is weak:

• Picking start and end is O(n²) on its own.
• Each check adds another walk of up to n steps.
• Total time is about O(n³). Too slow for a long string.
• You re-check the same letters again and again.

Here is the brute-force code for that idea:

def longest_palindrome(s):
    best = ""
    for left in range(len(s)):
        for right in range(left, len(s)):
            candidate = s[left:right + 1]
            if candidate == candidate[::-1] and len(candidate) > len(best):
                best = candidate
    return best

📊 Approach 2: Dynamic Programming Table (Better)

The idea in one line: a longer piece is a palindrome only if its inside is a palindrome and its two ends match.

The idea:

• Dynamic programming means we save answers to small pieces so we never solve them twice.
• Mark each piece as palindrome or not in a table.
• A piece i..j is a palindrome when s[i] == s[j] and the inside i+1..j-1 already is one.

How it works:

• Fill the table by length, from short pieces to long pieces.
• Single letters are palindromes. Two equal letters are too.
• Build longer answers from the shorter ones already marked.

Why it is weak:

• It needs a full table of size n by n.
• That costs O(n²) memory for no extra speed.
• Time is O(n²), same as the next idea, but it uses far more memory.

Here is the DP-table code for that idea:

def longest_palindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    best = ""

    for length in range(1, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            if s[left] == s[right] and (length <= 2 or dp[left + 1][right - 1]):
                dp[left][right] = True
                if length > len(best):
                    best = s[left:right + 1]

    return best

⚡ Approach 3: Expand Around Center (Best)

The idea in one line: every palindrome has a center, so stand at each center and grow outwards.

The idea:

• A palindrome like “aba” has a center letter “b”.
• A palindrome like “abba” has a center in the gap between the two “b” letters.
• So there are two center types: a single letter, and a gap between two letters.

How it works:

• From each center, push left and right at the same time.
• While the left letter equals the right letter, keep growing.
• The moment they differ, stop. Save the piece if it is the longest so far.

Why it is fast:

• There are about 2n centers, one on each letter and one in each gap.
• Each center grows at most n steps. So time is O(n²).
• It keeps only a best start and length, so extra memory is O(1).
• There is also Manacher’s algorithm at O(n), but it is rarely expected in an interview.

Here is the center trick drawn out as a dry run on "babad".

Steps to Solve

1. Keep track of the best start and best length found so far.
2. Walk through the string. Treat each index as a possible center.
3. For each index, expand around a single-letter center (odd length palindrome).
4. For each index, also expand around the gap between this letter and the next (even length palindrome).
5. While the left letter equals the right letter, move left one step back and right one step forward.
6. When the expansion stops, check if this palindrome is the longest so far. If yes, save its start and length.
7. After checking all centers, return the piece using the best start and best length.

#include <stdio.h>
#include <string.h>

int bestStart = 0;
int bestLen = 0;

// grow outwards while the two ends match
void expand(const char *s, int n, int left, int right) {
    while (left >= 0 && right < n && s[left] == s[right]) {
        left--;
        right++;
    }
    int len = right - left - 1;  // length after the last good match
    if (len > bestLen) {
        bestLen = len;
        bestStart = left + 1;
    }
}

void longestPalindrome(const char *s, char *out) {
    int n = (int)strlen(s);
    if (n == 0) { out[0] = '\0'; return; }
    bestStart = 0;
    bestLen = 1;
    for (int i = 0; i < n; i++) {
        expand(s, n, i, i);      // odd length center
        expand(s, n, i, i + 1);  // even length center
    }
    strncpy(out, s + bestStart, bestLen);
    out[bestLen] = '\0';
}

int main(void) {
    const char *s = "babad";
    char out[64];
    longestPalindrome(s, out);
    printf("%s\n", out);
    return 0;
}

bab

#include <iostream>
#include <string>
using namespace std;

int bestStart = 0;
int bestLen = 1;

void expand(const string& s, int left, int right) {
    int n = (int)s.size();
    while (left >= 0 && right < n && s[left] == s[right]) {
        left--;
        right++;
    }
    int len = right - left - 1;  // last valid length
    if (len > bestLen) {
        bestLen = len;
        bestStart = left + 1;
    }
}

string longestPalindrome(const string& s) {
    if (s.empty()) return "";
    bestStart = 0;
    bestLen = 1;
    for (int i = 0; i < (int)s.size(); i++) {
        expand(s, i, i);      // odd length center
        expand(s, i, i + 1);  // even length center
    }
    return s.substr(bestStart, bestLen);
}

int main() {
    string s = "babad";
    cout << longestPalindrome(s) << endl;
    return 0;
}

bab

public class LongestPalindrome {
    static int bestStart = 0;
    static int bestLen = 1;

    static void expand(String s, int left, int right) {
        int n = s.length();
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        int len = right - left - 1;  // last valid length
        if (len > bestLen) {
            bestLen = len;
            bestStart = left + 1;
        }
    }

    static String longestPalindrome(String s) {
        if (s.isEmpty()) return "";
        bestStart = 0;
        bestLen = 1;
        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);      // odd length center
            expand(s, i, i + 1);  // even length center
        }
        return s.substring(bestStart, bestStart + bestLen);
    }

    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome(s));
    }
}

bab

def longest_palindrome(s):
    if not s:
        return ""
    best_start, best_len = 0, 1

    def expand(left, right):
        # grow outwards while both ends match
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - left - 1  # start, length after stopping

    for i in range(len(s)):
        start1, len1 = expand(i, i)      # odd length center
        start2, len2 = expand(i, i + 1)  # even length center
        if len1 > best_len:
            best_start, best_len = start1, len1
        if len2 > best_len:
            best_start, best_len = start2, len2

    return s[best_start:best_start + best_len]


s = "babad"
print(longest_palindrome(s))

bab

function longestPalindrome(s) {
  if (s.length === 0) return "";
  let bestStart = 0;
  let bestLen = 1;

  function expand(left, right) {
    // grow outwards while both ends match
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return [left + 1, right - left - 1]; // start, length after stopping
  }

  for (let i = 0; i < s.length; i++) {
    const [start1, len1] = expand(i, i);     // odd length center
    const [start2, len2] = expand(i, i + 1); // even length center
    if (len1 > bestLen) {
      bestStart = start1;
      bestLen = len1;
    }
    if (len2 > bestLen) {
      bestStart = start2;
      bestLen = len2;
    }
  }

  return s.substring(bestStart, bestStart + bestLen);
}

const s = "babad";
console.log(longestPalindrome(s));

bab

Let us walk through the Python version line by line. This is the part interviewers love to hear out loud.

We start with if not s: return "". This guards against an empty string so nothing crashes later.

Then best_start, best_len = 0, 1. We assume the answer is at least one letter long, because any single letter is a palindrome by itself.

The inner expand function does the real work. It takes a left and a right. The while loop checks three things. The left index must stay inside the string. The right index must stay inside the string. And the two letters must match. While all three hold, we move left back and right forward. So the window grows from the center outwards.

When the loop stops, left and right have moved one step too far. So the real palindrome runs from left + 1 to right - 1. Its length is right - left - 1. We return both the start and the length.

In the main loop we call expand(i, i) for the odd case, where the center is a single letter. We also call expand(i, i + 1) for the even case, where the center is the gap between two letters. After each call we compare the length to our best so far. If it is longer we save the new start and length.

Finally s[best_start:best_start + best_len] slices out the winning piece. That slice is the longest palindromic substring.

⏱️ Time and Space Complexity

The brute force checks every piece and re-walks each one, so it is O(n³). Expand around center visits about 2n centers and grows each up to n steps, so it lands at O(n²) but uses almost no extra memory. The dynamic programming version is also O(n²) in time but it needs a full O(n²) table, so it trades memory for nothing extra here. That is why expand around center is the favorite in interviews.

🧩 Key Takeaways

• ✅ A palindrome reads the same forwards and backwards, and every palindrome has a center.
• ✅ Instead of checking every piece, stand at each center and grow outwards.
• ✅ There are two center types: a single letter, and the gap between two letters.
• ✅ Expand around center runs in O(n²) time with O(1) extra memory.
• ✅ Dynamic programming is also O(n²) but uses an O(n²) table, so it costs more memory.

🚀 What’s Next?

• Palindromic Substrings
• Isomorphic Strings