0170EasyHash TableStringSliding Window

Longest Twice-Only Stretch

Tracked in this browser only

Trains the technique from

LeetCode 3090Maximum Length Substring With Two Occurrences

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 vibration monitor writes one lowercase symbol per tick, and the whole shift arrives as the string log. Analysts study the shift by framing a stretch of consecutive ticks: a frame is picked by choosing a first tick and a last tick, and it keeps every tick between them with nothing skipped.

A frame is readable when no symbol inside it is written more than twice. A symbol that never appears in the frame is fine, one that appears once is fine, one that appears twice is fine, and a third appearance of the same symbol spoils the frame no matter how the ticks are spaced.

Work out the largest number of ticks a readable frame can span. A frame holding a single tick is always readable, so at least one frame always qualifies.

Examples

Example 1

Input: log = "mnmmnq"
Output: 5

The whole shift writes `m` three times, so it is not readable. Dropping the opening tick leaves `nmmnq`, where `n` appears twice, `m` twice and `q` once, spanning five ticks.

Example 2

Input: log = "zzz"
Output: 2

Any frame reaching all three ticks writes `z` a third time, so the best readable frame keeps two neighbouring ticks.

Example 3

Input: log = "cluster"
Output: 7

No symbol repeats anywhere in the shift, so the frame covering every tick is already readable.

Constraints

2 <= log.length <= 100
`log` 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_twice_only_stretch(log: str) -> int:

Java

public int longestTwiceOnlyStretch(String log)

The intended approach

Time O(n)Space O(1)

Slide a frame across the shift with two cursors and keep a tally of how often each symbol sits inside it. Extend the right cursor one tick at a time; the only way a frame can spoil is the symbol just added reaching a third appearance, so while that holds, drop ticks off the left cursor, which is exactly enough to make it readable again. Record the widest span the frame ever holds, and note the left cursor never needs to move back, so one pass suffices.

Pythonentry point: longest_twice_only_stretch

def longest_twice_only_stretch(log):
    # Time: O(n) -- both cursors only ever move forward across the log.
    # Space: O(1) -- tallies for the 26 lowercase symbols at most.
    tally = {}
    left = 0
    best = 0
    for right in range(len(log)):
        symbol = log[right]
        tally[symbol] = tally.get(symbol, 0) + 1
        while tally[symbol] > 2:
            tally[log[left]] -= 1
            left += 1
        if right - left + 1 > best:
            best = right - left + 1
    return best

The obvious version

Try every possible first tick, walk rightwards counting symbols, and stop that walk as soon as some symbol reaches a third appearance. Keep the longest readable span seen across all starts.

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_twice_only_stretch(log):
    n = len(log)
    best = 0
    for start in range(n):
        tally = {}
        for end in range(start, n):
            tally[log[end]] = tally.get(log[end], 0) + 1
            if tally[log[end]] > 2:
                break
            if end - start + 1 > best:
                best = end - start + 1
    return best

How this problem was checked

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