1194MediumHash TableStringPrefix Sum

The Longest Evenly Dyed Stretch

Tracked in this browser only

Trains the technique from

LeetCode 3714Longest Balanced Substring II

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 loom has laid down a run of dyed threads, threads spelling out the dye on each one as a, b or c.

A stretch of neighbouring threads is even when it holds as many a threads as b threads and as many b threads as c threads.

Return the number of threads in the longest even stretch, or 0 when no stretch of one thread or more is even.

Examples

Example 1

Input: threads = "abcabc"
Output: 6

Two of each dye across the whole run, so the whole run is even.

Example 2

Input: threads = "cabc"
Output: 3

The last three threads hold one of each dye. Taking the leading c as well would leave two c threads against one a thread.

Example 3

Input: threads = "aaabbbcc"
Output: 0

The run is three a threads, three b threads and two c threads. Any stretch reaching the c threads has already swallowed all three b threads, so no stretch ever balances and nothing qualifies.

Constraints

1 <= threads.length <= 10^5
threads holds only the characters a, b and c

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_balanced(threads: str) -> int:

Java

public int longestBalanced(String threads)

The intended approach

Time O(n) over the run.Space O(n) for the map of first sightings.

Counting inside a stretch is the same as taking a difference of two running counts, so keep running counts of the three dyes from the start of the run. A stretch is even when its `a` count equals its `b` count and its `b` count equals its `c` count, which in running terms says that `runA - runB` and `runB - runC` both come out the same at the two ends of the stretch. So a stretch is even exactly when the pair `(runA - runB, runB - runC)` repeats at the two ends. Walk the run once, and for each position work out that pair and look it up in a hash map holding the earliest position each pair was seen at. On a hit, the stretch from just after that earliest position to here is even, and pairing with the earliest sighting is what makes it the longest even stretch ending here. On a miss, record the position. The empty prefix, before any thread, has to go in the map as the pair `(0, 0)`, otherwise even stretches that start at the very first thread are missed. Nothing else is needed, and the answer is the longest hit found. It always comes out a multiple of three.

Pythonentry point: longest_balanced

def longest_balanced(threads):
    first = {(0, 0): -1}
    run_a = 0
    run_b = 0
    run_c = 0
    best = 0
    for at, dye in enumerate(threads):
        if dye == 'a':
            run_a += 1
        elif dye == 'b':
            run_b += 1
        else:
            run_c += 1
        key = (run_a - run_b, run_b - run_c)
        if key in first:
            span = at - first[key]
            if span > best:
                best = span
        else:
            first[key] = at
    return best

The obvious version

Weigh up every stretch. Start at each thread in turn and walk forward, keeping three counts as you go, and whenever all three agree note the length of the stretch reached so far against the best seen. Costs a walk to the end of the run from every starting thread.

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_balanced(threads):
    n = len(threads)
    best = 0
    for start in range(n):
        count_a = 0
        count_b = 0
        count_c = 0
        for at in range(start, n):
            dye = threads[at]
            if dye == 'a':
                count_a += 1
            elif dye == 'b':
                count_b += 1
            else:
                count_c += 1
            if count_a == count_b and count_b == count_c and at - start + 1 > best:
                best = at - start + 1
    return best

How this problem was checked

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