0638MediumHash TableStringDivide and ConquerSliding Window

Longest Solid Stretch Of The Intake Log

Tracked in this browser only

Trains the technique from

LeetCode 395Longest Substring with At Least K Repeating Characters

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.

An intake log is the lowercase string s, one letter per event, listed in the order the events arrived.

Take any stretch of consecutive events. Call the stretch solid when every letter that occurs anywhere inside it occurs at least k times inside it. Return the length of the longest solid stretch, or 0 when no non-empty stretch is solid.

Examples

Example 1

Input: s = "aaabbbddcaaabbbdd", k = 3
Output: 6

The stretch of events 0 through 5 spells aaabbb, where a occurs three times and b occurs three times, so it is solid and its length is 6.

Example 2

Input: s = "abcabc", k = 3
Output: 0

Each of a, b and c occurs twice in the whole log, so no letter reaches three occurrences anywhere and no non-empty stretch is solid.

Example 3

Input: s = "aabb", k = 2
Output: 4

The whole log holds a twice and b twice, which meets the requirement of at least two occurrences each, so the answer is its full length 4.

Constraints

1 <= s.length <= 10^4
s consists of only lowercase English letters.
1 <= k <= 10^5

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_substring(s: str, k: int) -> int:

Java

public int longestSubstring(String s, int k)

The intended approach

Time O(26 * n) — each of at most twenty-six rounds tallies every surviving position once.Space O(n) for the stack of pending segments plus the per-segment tally.

Keep a stack of candidate segments, starting with the whole log. Tally the letters of the segment on top. If no letter falls short of k occurrences the segment is solid and its length competes for the answer. Otherwise any letter that falls short cannot appear in a solid stretch lying inside this segment, so the segment is cut at every position holding such a letter and the surviving pieces are pushed back for the same treatment. Every cut drops at least one distinct letter from the pieces, so a position is examined at most twenty-six times. A segment already shorter than the best length found is discarded unexamined.

Pythonentry point: longest_substring

def longest_substring(s, k):
    # O(26 * n) time, O(n) space. Work on segments held in an explicit stack. For
    # a segment, tally its letters. If none is short of k occurrences the whole
    # segment is solid and its length is a candidate. Otherwise every letter that
    # is short can never be part of a solid stretch inside this segment, so the
    # segment is cut at each of their positions and the pieces go back on the
    # stack. Each cut removes at least one distinct letter, so a piece is
    # revisited at most 26 times.
    best = 0
    stack = [(0, len(s))]
    while stack:
        lo, hi = stack.pop()
        if hi - lo < k or hi - lo <= best:
            continue
        cnt = {}
        for i in range(lo, hi):
            ch = s[i]
            cnt[ch] = cnt.get(ch, 0) + 1
        short = set()
        for ch in cnt:
            if cnt[ch] < k:
                short.add(ch)
        if not short:
            best = hi - lo
            continue
        start = lo
        for i in range(lo, hi):
            if s[i] in short:
                if i > start:
                    stack.append((start, i))
                start = i + 1
        if start < hi:
            stack.append((start, hi))
    return best

The obvious version

Take every pair of start and end positions, tally the letters of that stretch from scratch, check that no tally falls short of k, and keep the longest stretch that passes.

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_substring(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        for end in range(start + 1, n + 1):
            cnt = {}
            for ch in s[start:end]:
                cnt[ch] = cnt.get(ch, 0) + 1
            ok = True
            for ch in cnt:
                if cnt[ch] < k:
                    ok = False
                    break
            if ok and end - start > best:
                best = end - start
    return best

How this problem was checked

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