1185HardHash TableStringSorting

The Longest Sealed Stretch of the Ribbon

Tracked in this browser only

Trains the technique from

LeetCode 3104Find Longest Self-Contained Substring

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 ribbon ribbon holds lowercase letters. A stretch of neighbouring letters is sealed when it is not the whole ribbon and no letter appearing inside it appears anywhere outside it.

Return the length of the longest sealed stretch, or -1 when the ribbon has none.

Examples

Example 1

Input: ribbon = "baab"
Output: 2

The two middle letters are the only a on the ribbon, so that stretch is sealed. Reaching any further pulls in a b that also stands outside.

Example 2

Input: ribbon = "abbcca"
Output: 4

The four middle letters hold only b and c, and neither appears outside them, so a stretch of four is sealed.

Example 3

Input: ribbon = "aa"
Output: -1

The only stretch holding every a is the whole ribbon, which does not count.

Constraints

2 <= ribbon.length <= 5 * 10^4
ribbon holds only lowercase English letters

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 max_substring_length(ribbon: str) -> int:

Java

public int maxSubstringLength(String ribbon)

The intended approach

Time O(26n) over the ribbon.Space O(1), since only twenty-six letters exist.

A sealed stretch is pinned down by two facts about the letters inside it: none of them appears before the stretch begins, and none appears after it ends. So for each letter note where it first and last appears. The left end of a sealed stretch is always the first appearance of the letter standing there, since otherwise that letter would appear before the stretch. There are at most twenty-six such positions, one per letter, so only twenty-six left ends need trying. Fix one and sweep the right end outwards, carrying the earliest first appearance and the latest last appearance among the letters met so far. The stretch is sealed exactly when the earliest first appearance is not before the left end and the latest last appearance lands on the right end, which is what says nothing inside spills either way. Record the length whenever that holds and the stretch is not the whole ribbon.

Pythonentry point: max_substring_length

def max_substring_length(ribbon):
    n = len(ribbon)
    first = {}
    last = {}
    for i in range(n):
        ch = ribbon[i]
        if ch not in first:
            first[ch] = i
        last[ch] = i
    best = -1
    for ch in first:
        l = first[ch]
        low = n
        high = -1
        for r in range(l, n):
            f = first[ribbon[r]]
            if f < low:
                low = f
            e = last[ribbon[r]]
            if e > high:
                high = e
            if low >= l and high == r:
                span = r - l + 1
                if span < n and span > best:
                    best = span
    return best

The obvious version

Take every stretch of the ribbon outright, gather the letters it holds, and walk the whole ribbon outside it checking that none of those letters turns up, keeping the longest stretch that passes and is not the whole ribbon. Costs the ribbon length cubed.

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_max_substring_length(ribbon):
    n = len(ribbon)
    best = -1
    for l in range(n):
        for r in range(l, n):
            if r - l + 1 == n:
                continue
            inside = set(ribbon[l:r + 1])
            ok = True
            for i in range(n):
                if l <= i and i <= r:
                    continue
                if ribbon[i] in inside:
                    ok = False
                    break
            if ok and r - l + 1 > best:
                best = r - l + 1
    return best

How this problem was checked

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