# Palindrome Hunt

> It reads the same both ways. Go further.

Canonical URL: <https://datadriven.io/problems/palindrome_hunt>

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Given a string, return the longest palindromic substring. If multiple tie for longest, return the one with the smallest starting index.

## Worked solution and explanation

### Why this problem exists in real interviews

Finding the longest palindromic substring tests **expand-around-center** logic, a technique that requires handling both odd and even length palindromes. It is a mid-level string problem that separates candidates who know O(n^2) center expansion from those who attempt brute-force O(n^3).

> **Trick to Solving**
>
> For each index, treat it as the center of a potential palindrome and expand outward while characters match. Do this for both odd-length (single center) and even-length (two-character center) palindromes. Track the longest found.

---

### Break down the requirements

#### Step 1: Try each position as a palindrome center

Both single characters (odd length) and adjacent pairs (even length) can be centers.

#### Step 2: Expand while characters match

From each center, move left and right pointers outward while `s[left] == s[right]`.

#### Step 3: Track the longest palindrome found

Update the best start and end indices whenever a longer palindrome is discovered.

---

### The solution

**Expand-around-center for longest palindromic substring**

```python
def longest_palindrome(s):
    if not s:
        return ''
    best_start = 0
    best_len = 1
    for center in range(len(s)):
        left = center
        right = center
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > best_len:
                best_start = left
                best_len = right - left + 1
            left -= 1
            right += 1
        left = center
        right = center + 1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > best_len:
                best_start = left
                best_len = right - left + 1
            left -= 1
            right += 1
    result = s[best_start:best_start + best_len]
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n^2) where n is the string length. Each center expansion is O(n) and there are O(n) centers.
> 
> **Space:** O(1) excluding the output string. Only index variables are used.

> **Interviewers Watch For**
>
> Whether you handle both odd and even length palindromes. Missing the even-length case is a common oversight that fails on inputs like `'abba'`.

> **Common Pitfall**
>
> Using a brute-force O(n^3) approach that checks every substring. This works but is too slow for strings of length 1000.

---

## Common follow-up questions

- Can you solve this in O(n) time? _(Tests knowledge of Manacher's algorithm, which uses previously computed palindrome radii to skip redundant comparisons.)_
- What if you needed to count all palindromic substrings? _(Tests modifying center expansion to count rather than track the longest.)_
- What if the palindrome check should be case-insensitive? _(Tests normalizing the string to lowercase before processing.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/palindrome_hunt)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.