InternDoor

Longest mirror inside a word

Mediumstrings · two pointers · dynamic programming

Reported in interviews at (where)

A palindrome reads the same backwards as forwards. Given a string s, return its longest piece (characters next to each other) that is a palindrome.

If several pieces share the longest length, return the one that starts first.

Example 1
Input
s = "bananas"
Output
"anana"

"anana" reads the same both ways; nothing longer does.

Example 2
Input
s = "abcd"
Output
"a"

Every single letter is a palindrome; "a" starts first.

Example 3
Input
s = "xyyx7"
Output
"xyyx"

An even-length mirror.

Limits

  • 1 <= s.length <= 2000
  • s holds lowercase English letters and digits.

Hints

Hint 1

Every palindrome has a centre: a letter, or the gap between two letters.

Hint 2

Grow outwards from each of the 2n - 1 centres.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.