Show problems as
Classic problem #214HardStringRolling HashString MatchingHash FunctionManacherZ AlgorithmKnuth–Morris–Pratt Algorithm

Shortest Palindrome

Real-world version: Bead Strand Mirror
Tracked in this browser only
Read Shortest Palindrome on LeetCode(opens in a new tab)

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

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

Python
def shortest_palindrome(strand: str) -> str:
Java
public String shortestPalindrome(String strand)

More on the same topics