0010MediumTwo PointersStringDynamic Programming

Longest Mirror Run

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_mirror_run(tag: str) -> str:

Java

public String longestMirrorRun(String tag)

The intended approach

Time O(n^2)Space O(1)

A mirror run grows outward from a middle, which is either one character or the gap between two characters. Walk every one of those 2n - 1 middles left to right, push both ends apart while they agree, and keep the widest span seen. Updating only on a strictly wider span means the earliest of several equally wide runs is the one kept.

Pythonentry point: longest_mirror_run

def longest_mirror_run(tag):
    n = len(tag)
    best_start, best_len = 0, 1
    for center in range(n):
        for left, right in ((center, center), (center, center + 1)):
            while left >= 0 and right < n and tag[left] == tag[right]:
                left -= 1
                right += 1
            span = right - left - 1
            if span > best_len:
                best_len = span
                best_start = left + 1
    return tag[best_start:best_start + best_len]

The obvious version

Cut out every slice, reverse it and compare, keeping the widest match found while scanning start indices in increasing order. O(n^3).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_mirror_run(tag):
    best = tag[:1]
    n = len(tag)
    for i in range(n):
        for j in range(i, n):
            piece = tag[i:j + 1]
            if len(piece) > len(best) and piece == piece[::-1]:
                best = piece
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in