The O(n) Club: Longest Palindromic Substring — The Algorithm That Reads the Same Backwards (and Forwards, Duh)

The O(n) Club: Longest Palindromic Substring — The Algorithm That Reads the Same Backwards (and Forwards, Duh)

⚡ TL;DR

Need to impress an interviewer with your love for mirrored text? Find the longest substring in a string that’s the same forwards and backwards. Brute force exists, but so does waiting in line at the DMV. Here’s the terrifying approach:

// Brute force: Tell your CPU “good luck”
String res = "";
for (int i = 0; i < s.length(); i++) {
    for (int j = i + 1; j <= s.length(); j++) {
        String sub = s.substring(i, j);
        if (isPalindrome(sub) && sub.length() > res.length()) {
            res = sub;
        }
    }
}
return res;

🧠 How Devs Usually Mess This Up

Ah yes, the proud tradition of confusing substrings with subsequences—and skipping even-length palindromes entirely, as if “abba” wasn’t cool enough. Or worse, trying every single substring and accidentally inventing crypto-mining on your laptop. Remember: only contiguous substrings count. No scattergories allowed.

🔍 What’s Actually Going On

Think of a palindrome as your code editor in dark mode: everything’s about balance and mirror images. The magic move? Every palindrome has a center (sometimes between two letters). Just expand outward from there until the mirage shatters. Check all single letters and all pairs, because symmetry has feelings too. Imagine a chef slicing a sandwich—sometimes you slice through the bread, sometimes right between the slices. That’s how you find all the tasty centers.

🛠️ PseudoCode

• For every index in the string:
• Expand from s[i] for odd lengths.
• Expand from between s[i] and s[i+1] for even lengths.
• Whenever you find a longer palindrome, memorize its start/end points.
• Return your best work at the end. (We’re not monsters.)

// Expand helper (Java-ified pseudo)
int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length()
           && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

💻 The Code

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}
 private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length()
           && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Substring vs subsequence. Interviewers are watching, and so is karma.
• Only checking odd-length palindromes will leave “noon” feeling left out. Support both flavors!
• Single-char or empty input? Return what you got—don’t throw a dramatic Java exception.
• Center-expansion runs in O(n²), but actual humans won’t notice. Brute force? Good luck explaining your AWS bill.
• If someone drops “Manacher’s algorithm,” just nod and change the subject to pizza.

🧠 Interviewer Brain-Tattoo

“Expand around the center—of strings and of your own self-esteem. Both are more effective than brute force.”