0696HardStringRolling HashString MatchingHash FunctionZ AlgorithmKnuth–Morris–Pratt Algorithm

Longest Overlapping Border

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 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 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_border(tape: str) -> str:

Java

public String longestBorder(String tape)

The intended approach

Time O(n) for a label of n letters: the fallback total is bounded by the number of letters.Space O(n) for the table of border lengths, plus the returned string.

Build, for every prefix of the label, the length of that prefix's own longest border, in a single left-to-right pass. Each new letter either extends the length carried over from the previous prefix, or forces a fall back to the border of the stretch already matched, which is the next shorter candidate that could still work. The entry for the last position is the answer's length, so the answer is that many letters off the front.

Pythonentry point: longest_border

def longest_border(tape):
    n = len(tape)
    # span[i] = length of the longest border of the label's first i + 1 letters
    span = [0] * n
    matched = 0
    for i in range(1, n):
        # on a mismatch fall back to the border of the part already matched,
        # which is the next shorter candidate worth trying
        while matched and tape[i] != tape[matched]:
            matched = span[matched - 1]
        if tape[i] == tape[matched]:
            matched += 1
        span[i] = matched
    return tape[:span[n - 1]]

The obvious version

Try candidate lengths from one below the label length downwards, and for each one compare the leading letters against the trailing letters outright. The first length that matches gives the answer. Quadratic in the label length.

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_border(tape):
    n = len(tape)
    for length in range(n - 1, 0, -1):
        if tape[:length] == tape[n - length:]:
            return tape[:length]
    return ""

How this problem was checked

Reference solution executed against 14 test cases — 14 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