Subarrays with K Different Integers
Real-world version: Stretches Using Exactly K SpoolsThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def stretches_with_k_spools(stitches: list[int], k: int) -> int:public int stretchesWithKSpools(int[] stitches, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's