You’re in a coding interview. The interviewer gives you "babad" and asks for the longest palindromic substring. You start checking every substring, realize there are O(n^2) of them, each taking O(n) to verify, and your brute force is O(n^3). The interviewer says: “Can you do better?” You know there’s a trick involving expanding from centers, but you only handle odd-length palindromes and miss "bb" entirely. Now you’re debugging a missing case with the clock running.

This walkthrough covers how to avoid that trap: the expand-around-center technique that handles both odd and even palindromes cleanly, why it’s O(n^2) with O(1) space, and the off-by-one errors that silently break most implementations.

---

The Problem

Given a string s, return the longest substring of s that is a palindrome. A palindrome reads the same forwards and backwards. If there are multiple answers of the same maximum length, return any one of them.

(LeetCode #5)

Example

Input s = "babad"

Output "bab" (or "aba", both are valid)

Explanation: Both "bab" and "aba" are palindromic substrings of length 3. No substring of length 4 or 5 is a palindrome. Another example: for s = "cbbd", the output is "bb".

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
Approach breadth	Do you know multiple strategies and compare their trade-offs?
String intuition	Do you naturally think about odd vs. even length palindromes?
Optimization thinking	Can you move from O(n^3) to O(n^2) with clear reasoning?
Communication	Do you explain why an approach works, not just what it does?
Edge case handling	Do you catch single-character strings and all-same-character strings?

---

Step 1: Clarifying Questions

1. Can the string be empty? Clarify the base case. Likely return "".

2. Is the answer case-sensitive? The problem assumes lowercase letters, but confirming shows attention to detail.

3. Should I return the substring itself, or just its length? The problem asks for the substring. Knowing early helps you design the return value.

4. Are there multiple valid answers? If two substrings tie, you can return either. Explicitly allowed.

5. What’s the expected input size? For N up to 1000+, you need O(n^2) or better. O(n^3) brute force won’t scale.

---

Step 2: A First (Non-Optimal) Idea

Check every possible substring and test whether it’s a palindrome.

def is_palindrome(s, left, right):
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

def longest_palindrome_brute(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i + 1, n):
            if j - i + 1 > best_len and is_palindrome(s, i, j):
                best_start = i
                best_len = j - i + 1
    return s[best_start : best_start + best_len]

O(n^2) substrings x O(n) palindrome check = O(n^3). Unacceptable for large inputs. Mention it, explain why it won’t scale, and transition.

---

Step 3: The Key Insight

Instead of checking each substring from the outside in, expand outward from each center. Every palindrome has a center: a single character for odd-length ("racecar" centered on e), or the gap between two characters for even-length ("abba" centered between b and b). There are 2n-1 centers total. Expanding from each takes at most O(n), giving O(n^2) overall with O(1) space.

This is the core technique. Handle both center types explicitly.

---

Step 4: Optimal Strategy

1. Initialize best_start = 0, best_len = 1.
2. For each index i from 0 to n-1:
   • Expand around center i (odd-length palindrome).
   • Expand around centers i and i+1 (even-length palindrome).
3. In each expansion, use two pointers expanding while s[left] == s[right].
4. After each expansion, update the best if the palindrome is longer.
5. Return s[best_start : best_start + best_len].

---

Python Implementation

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        best_start = 0
        best_len = 1

        def expand(left: int, right: int) -> None:
            nonlocal best_start, best_len
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # After loop, valid palindrome is s[left+1 : right]
            current_len = right - left - 1
            if current_len > best_len:
                best_len = current_len
                best_start = left + 1

        for i in range(len(s)):
            expand(i, i)       # Odd-length palindrome centered at i
            expand(i, i + 1)   # Even-length palindrome centered between i and i+1

        return s[best_start : best_start + best_len]

Why left + 1 and right - left - 1? When the while loop exits, s[left] != s[right] (or we hit a boundary). The actual palindrome starts at left + 1 and has length right - left - 1.

---

Time & Space Complexity

Aspect	Complexity	Explanation
Time	O(n^2)	n centers, each expansion takes at most O(n)
Space	O(1)	Only a constant number of variables

Bonus: There’s an O(n) algorithm called Manacher’s Algorithm. Mentioning it shows algorithmic breadth, but implementing it under interview pressure is usually not expected.

---

Common Interview Mistakes

1. Forgetting even-length palindromes. The single most common bug. Only expanding from single characters misses palindromes like "abba" or "bb". Always handle both center types.

2. Off-by-one errors in the expansion result. When the loop exits, the pointers have gone one step too far. The palindrome is s[left+1 : right], not s[left : right+1].

3. Coding O(n^3) brute force without acknowledging it. Presenting brute force is fine as a starting point, but failing to recognize it won’t scale is a red flag.

4. Jumping into DP without knowing why. Some candidates recall this is a “DP problem” and start drawing a 2D table without articulating the recurrence. The expand-around-center approach is simpler and just as optimal.

5. Not explaining the two center types. Saying “I expand from the center” without clarifying odd vs. even suggests shallow understanding.

6. Mishandling empty string or single-character input. A single character is always a palindrome of length 1. An empty string should return "".

---

What a Strong Candidate Sounds Like

“The brute force checks every substring in O(n^3). To do better, I’ll expand around every possible center. A palindrome has a center: a single character for odd-length, or the gap between two characters for even-length. There are 2n-1 centers, and each expansion costs at most O(n), giving O(n^2) time with O(1) space. I’ll handle both odd and even centers explicitly in my expand helper.”

---

Example Interview Dialogue

Interviewer: Why 2n-1 centers?

Candidate: For a string of length n, there are n positions that can be the center of an odd-length palindrome (one per character) and n-1 gaps between characters for even-length palindromes. Total: n + (n-1) = 2n-1.

Interviewer: Can you do better than O(n^2)?

Candidate: Yes, Manacher’s Algorithm runs in O(n) by reusing previously computed palindrome lengths. It’s fairly involved to implement. I know how it works conceptually, but I’d want to confirm you want me to implement it rather than the expand-around-center approach.

---

Related Problems to Practice

These problems all build on palindrome reasoning and string techniques:

• Palindromic Substrings (LeetCode #647). Count all palindromic substrings. Same expand-around-center technique, different aggregation.
• Longest Palindromic Subsequence (LeetCode #516). Harder DP variant where characters don’t need to be contiguous.
• Palindrome Partitioning (LeetCode #131). Combines palindrome checking with backtracking.
• Valid Palindrome (LeetCode #125). Simpler warm-up. Good for building intuition.
• Minimum Insertion Steps to Make a String Palindrome (LeetCode #1312). Hard DP problem closely related to palindrome structure.

---

Practice This in a Mock Interview

Understanding the expand-around-center technique on paper is a great start. But under timed pressure, you need to verbalize your reasoning, handle follow-up questions, catch off-by-one bugs live, and manage your pace. That’s a fundamentally different challenge from reading a walkthrough.

Start a mock interview for Longest Palindromic Substring on Intervu.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code