0187HardArrayHash TableSliding WindowCounting

Stretches Using Exactly K Spools

Tracked in this browser only

Trains the technique from

LeetCode 992Subarrays with K Different Integers

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 records which yarn spool it drew from for each stitch it makes, in the order the stitches were made, as the array stitches. Spools are labelled from 1 up to the number of stitches on the strip.

A stretch is a run of neighbouring stitches with nothing skipped in the middle. Count the stretches that draw on exactly k different spools.

Two stretches count separately whenever they start or end at different stitches, even if the spools they use happen to be the same. Return that count.

Examples

Example 1

Input: stitches = [4, 4, 2, 4], k = 2
Output: 5

The qualifying stretches run over stitches 1-3, 1-4, 2-3, 2-4 and 3-4; every other stretch touches just one spool.

Example 2

Input: stitches = [3, 3, 3], k = 1
Output: 6

One spool made the whole strip, so all six stretches qualify.

Example 3

Input: stitches = [2, 2], k = 2
Output: 0

Only one spool appears anywhere on the strip, so no stretch can reach two.

Constraints

1 <= stitches.length <= 2 * 10^4
1 <= stitches[i] <= stitches.length
1 <= k <= stitches.length

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 stretches_with_k_spools(stitches: list[int], k: int) -> int:

Java

public int stretchesWithKSpools(int[] stitches, int k)

The intended approach

Time O(n)Space O(k)

Counting stretches with a distinct-spool count of exactly k directly is awkward, but counting those with at most a given bound is easy with one window: hold a tally of spools inside the window, advance the right edge, and pull the left edge forward until the bound holds again, at which point every stretch ending at the right edge and starting at or after the left edge qualifies. Running that for k and for k minus one and subtracting leaves precisely the stretches that hit k.

Pythonentry point: stretches_with_k_spools

def stretches_with_k_spools(stitches, k):
    # Stretches using at most k spools, minus those using at most k - 1, leaves
    # exactly those using k. Each bound is one sliding window whose left edge
    # only ever moves forward, and a window ending at right that satisfies the
    # bound contributes right - left + 1 stretches.
    # Time O(n). Space O(k) for the counts inside the window.
    def at_most(limit):
        if limit <= 0:
            return 0
        counts = {}
        left = 0
        total = 0
        for right in range(len(stitches)):
            spool = stitches[right]
            counts[spool] = counts.get(spool, 0) + 1
            while len(counts) > limit:
                dropped = stitches[left]
                counts[dropped] -= 1
                if counts[dropped] == 0:
                    del counts[dropped]
                left += 1
            total += right - left + 1
        return total

    return at_most(k) - at_most(k - 1)

The obvious version

Fix each starting stitch and walk forward, collecting spools in a set and adding one to the tally whenever the set is the right size, abandoning the start once the set overshoots. O(n^2).

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_stretches_with_k(stitches, k):
    n = len(stitches)
    total = 0
    for start in range(n):
        seen = set()
        for end in range(start, n):
            seen.add(stitches[end])
            if len(seen) == k:
                total += 1
            elif len(seen) > k:
                break
    return total

How this problem was checked

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