Longest Mirror Substring

Medium1-D Dynamic Programming

Problem

Given a lowercase string s, return its longest substring that reads the same forwards and backwards.

If several substrings share the maximum length, return the one that starts leftmost.

Example 1

Input:
s = "bananas"
Output:
"anana"

Example 2

Input:
s = "abcd"
Output:
"a"

All single letters tie at length 1; the leftmost is "a".

Example 3

Input:
s = "abacab"
Output:
"bacab"

"aba" has length 3, but "bacab" has length 5.

Constraints

  • 1 ≤ s.length ≤ 1000
  • s contains lowercase English letters.

Hint

Show the first hint

Reuse the mirror test: s[i..j] is a mirror iff s[i] == s[j] and s[i+1..j-1] is a mirror.

Walkthrough

How to approach it

01Clarify before coding

  • What if several have the same length? Return the leftmost one.
  • Is a single character a valid answer? Yes; the string is never empty.
  • Return the substring or its indices? The substring itself.

02Brute force

Check every substring by reversing it and keep the longest.

Cost: O(n³): about 1.7·10^8 character operations at n = 1000.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.