Show problems as
Classic problem #1392HardStringRolling HashString MatchingHash FunctionZ AlgorithmKnuth–Morris–Pratt Algorithm

Longest Happy Prefix

Real-world version: Longest Overlapping Border
Tracked in this browser only
Read Longest Happy Prefix on LeetCode(opens in a new tab)

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

A reel of tape carries a label written in lowercase letters, given as tape.

A border of the label is a string that is at the same time a prefix of the label and a suffix of the label, and that is strictly shorter than the whole label. The empty string is a border of every label.

Return the longest border of tape. When the empty string is the only border, return the empty string.

Examples

Example 1

Input
tape = "abababab"
Output
"ababab"

The label opens with `ababab` and closes with `ababab`, and that string is shorter than the label itself.

Example 2

Input
tape = "abcd"
Output
""

The label opens with `a` and closes with `d`, so no string of one or more letters is both a prefix and a suffix. The empty string is returned.

Example 3

Input
tape = "aabaa"
Output
"aa"

The label opens with `aa` and closes with `aa`, and that string is shorter than the label itself.

Constraints

  • 1 <= tape.length <= 10^5
  • tape 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 longest_border(tape: str) -> str:
Java
public String longestBorder(String tape)

More on the same topics