# Reads The Same Both Ways

> Somewhere in the noise, a stretch that mirrors itself. Find the longest one.

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

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Auditing free-text fields in a data export, you need the longest contiguous stretch of a string `s` that reads the same forwards and backwards. If several stretches tie for that maximum length, return the one with the smallest starting index.

## Worked solution and explanation

### What this really is

Strip the business costume and this is the longest-palindromic-substring problem, and the trap is hiding in plain sight: a palindrome can have an even length. Candidates who picture only odd palindromes anchor on a single center character and quietly miss every 'abba' shaped answer. The skill being probed is whether you can grow a match outward from a center while tracking the best span, for both the odd and even case, without paying for an O(n^3) substring scan.

> **Trick to solving**
>
> Treat each position as the center of a mirror and grow outward while the two ends match. Do it twice per index: once with a single-character center (odd length) and once with a two-character center (even length). Keep the longest span you see.

---

### How to get there

#### Step 1: Use each position as a center, both parities

Every index is a candidate center. The even case is the one people forget: the center sits between two characters, so seed it with left=center and right=center+1.

#### Step 2: Grow while the ends match

From a center, step left and right outward as long as both ends are in bounds and `s[left] == s[right]`. The moment they differ, that span is done.

#### Step 3: Keep the best span, earliest wins ties

Record start and length only when you beat the current best. Because you scan centers left to right and only replace on a strictly longer span, the earliest start wins ties for free, which is exactly the requested tie-break.

---

### The solution

**Expand around center, odd and even**

```python
def palindrome_hunt(s):
    best_start = 0
    best_len = 1
    for center in range(len(s)):
        for left, right in ((center, center), (center, 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
    return s[best_start:best_start + best_len]
```

*The inner tuple runs both parities through identical expansion logic, so the even case can never be forgotten.*

> **Cost**
>
> **Time:** O(n^2). There are n centers and each expands at most O(n). **Space:** O(1) beyond the returned slice, since only index variables are tracked. For n up to 1000 this is roughly a million comparisons worst case, instant in practice.

> **Interviewers watch for**
>
> The single tell that separates a mid from a senior here is the even-length center. If you only seed (center, center) you will sail through 'racecar' and then fail 'abba'. Saying out loud 'I handle both parities' before you write the loop is the signal.

> **Common pitfall**
>
> Checking every substring for the palindrome property is O(n^3) and the obvious first instinct. It passes tiny tests and dies on the 1000-character inputs. Reach for center expansion before anyone has to ask you to speed it up.

---

## Common follow-up questions

- Can you push this to O(n) time? _(Tests knowledge of Manacher's algorithm, which reuses previously computed palindrome radii to skip redundant comparisons.)_
- What if you needed to count every palindromic substring instead of finding the longest? _(Tests adapting center expansion to accumulate a count instead of tracking a single best span.)_
- How would you make the match case-insensitive or ignore non-letters? _(Tests normalizing the input before the expansion runs.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/reads_the_same_both_ways)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.