0382HardStringRolling HashString MatchingHash FunctionManacherZ AlgorithmKnuth–Morris–Pratt Algorithm

Bead Strand Mirror

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 strung necklace is described by strand, a string of lowercase letters naming the bead colours from the clasp end outwards. The far end of the strand is already knotted, so beads can be threaded on only at the clasp end -- that is, characters may be inserted before strand, and the letters of strand keep their order and stay at the back of the result.

A strand is mirrored when it reads the same colour sequence in either direction. Return the shortest mirrored strand that can be produced this way.

Examples

Example 1

Input: strand = "abab"
Output: "babab"

Threading one b at the clasp end gives "babab", which reads the same in either direction.

Example 2

Input: strand = "wxyz"
Output: "zyxwxyz"

Threading z, y and x at the clasp end gives "zyxwxyz", and the four original beads still sit at the back in their original order.

Example 3

Input: strand = "aabb"
Output: "bbaabb"

Threading b and b gives "bbaabb", which reads the same in either direction.

Example 4

Input: strand = "abcba"
Output: "abcba"

The strand already reads the same in either direction, so nothing is threaded on.

Constraints

0 <= strand.length <= 5 * 10^4
strand consists of lowercase English letters only.

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 shortest_palindrome(strand: str) -> str:

Java

public String shortestPalindrome(String strand)

The intended approach

Time O(n)Space O(n) for the prefix table and the returned strand

Whatever is threaded on at the clasp end must mirror the tail of `strand`, so the answer is fixed by the longest front section of `strand` that is already mirrored: everything after it gets reversed and threaded on. To find that length in linear time, build the probe `strand + '|' + reverse(strand)` and run the prefix-function of Knuth-Morris-Pratt over it; its last entry is the length of the longest prefix of `strand` that is also a suffix of the reversal, which is exactly the longest mirrored front section. The separator keeps a match from spanning the join.

Pythonentry point: shortest_palindrome

def shortest_palindrome(strand):
    # Time O(n) -- one prefix-function pass over a probe of length 2n + 1.
    # Space O(n) for the prefix table and the returned strand.
    n = len(strand)
    if n <= 1:
        return strand
    probe = strand + "|" + strand[::-1]
    fail = [0] * len(probe)
    k = 0
    for i in range(1, len(probe)):
        ch = probe[i]
        while k and probe[k] != ch:
            k = fail[k - 1]
        if probe[k] == ch:
            k += 1
        fail[i] = k
    keep = fail[-1]
    return strand[keep:][::-1] + strand

The obvious version

Try every front section from the whole strand downwards, testing each directly against its own reversal, and stop at the first one that reads the same both ways. Quadratic, with no prefix table.

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_shortest_palindrome(strand):
    for keep in range(len(strand), -1, -1):
        head = strand[:keep]
        if head == head[::-1]:
            return strand[keep:][::-1] + strand
    return strand

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 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