Reads The Same Both Ways

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Slalom

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.

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

Example 1

Input:

s = "racecarx"

Output:

"racecar"

Example 2

Input:

s = "abcba"

Output:

"abcba"

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.

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
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.

Common follow-up questions