Show problems as
Classic problem #5MediumTwo PointersStringDynamic Programming

Longest Palindromic Substring

Real-world version: Longest Mirror Run
Tracked in this browser only
Read Longest Palindromic Substring on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstTwo Pointers · Strings, animated step by step

A firmware pipeline stamps every build artifact with an alphanumeric label tag, made up only of digits and English letters.

Call a contiguous slice of tag a mirror run when the slice is identical to itself written back to front. Characters are compared exactly as they appear, so T and t never match.

Return the longest mirror run contained in tag. When two or more mirror runs are tied for longest, hand back the one whose first character sits at the lowest index.

Examples

Example 1

Input
tag = "kayak7pop"
Output
"kayak"

The slice `kayak` covers indices 0 through 4 and mirrors itself; `pop` also mirrors but is shorter.

Example 2

Input
tag = "9m4tt4z"
Output
"4tt4"

Here the widest mirror run has even width, sitting between the two `t` characters.

Example 3

Input
tag = "aA"
Output
"a"

Case matters, so the two characters do not mirror each other and the earliest single character wins.

Constraints

  • 1 <= tag.length <= 1000
  • tag contains digits and English letters only (both cases allowed)
  • Ties at the maximum width are broken by the lowest starting index

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_mirror_run(tag: str) -> str:
Java
public String longestMirrorRun(String tag)

More on the same topics