Longest stretch that reads the same backwards

Strings and tries Mid-level Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
text = "xabbay"
lo, hi = 2, 3
while 0 <= lo and hi < len(text) and text[lo] == text[hi]:
    lo, hi = lo - 1, hi + 1
print(text[lo + 1:hi], lo, hi)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A abba 0 5

Right: expansion stops when x and y differ, one step past the match.

The loop always ends one step beyond the last match, which is why the slice starts at lo + 1.

Why not the others?
  • B abba 1 4. The loop moves lo and hi once more before the failing check.
  • C bb 1 4. a and a also match around the bb centre.

30-second answer

Every such stretch has a centre: a letter (odd length) or the gap between two letters (even length). For each of the 2n - 1 centres, expand outward while the ends match, and keep the longest. O(n²) time and O(1) extra memory, with simple code.

Practise saying it · 45 s. No recording, just a timer

Explain expanding around centres.

Say your answer out loud, then check which of these points you covered:

  • 2n - 1 centres
  • Expand while ends match
  • O(n²)

Deep dive

Expanding around centres is the template for 'reads the same backwards' inside strings.

Manacher's algorithm does it in O(n) but is rarely expected in interviews.

Visiting centres left to right and replacing only on strictly longer keeps the leftmost answer.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def longest_mirror(text: str) -> str:
    best_start, best_len = 0, 0
    for centre in range(2 * len(text) - 1):  # letters and gaps
        lo, hi = centre // 2, centre // 2 + centre % 2
        while 0 <= lo and hi < len(text) and text[lo] == text[hi]:
            lo, hi = lo - 1, hi + 1
        size = hi - lo - 1  # the last pair that matched
        if size > best_len:
            best_start, best_len = lo + 1, size
    return text[best_start:best_start + best_len]

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun longestMirror(text: String): String {
    var bestStart = 0
    var bestLen = 0
    for (centre in 0 until 2 * text.length - 1) { // letters and gaps
        var lo = centre / 2
        var hi = centre / 2 + centre % 2
        while (lo >= 0 && hi < text.length && text[lo] == text[hi]) {
            lo--
            hi++
        }
        val size = hi - lo - 1
        if (size > bestLen) {
            bestStart = lo + 1
            bestLen = size
        }
    }
    return text.substring(bestStart, bestStart + bestLen)
}

Common mistakes

  • Handling only odd lengths and missing 'abba'.
  • Checking every substring separately, which is O(n³).

Senior take & follow-ups

Mention the even-length centres before you start; it is the usual slip.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you count all such stretches?

    Show hint

    Same expansion, adding one for each successful step.

  2. What is Manacher's idea?

    Show hint

    Reuse the mirror of an earlier expansion to skip comparisons, giving O(n).

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.