Free Strings lessonsStrings · Stage 5 · Mastery · Step 4

Exactly k kinds

Count the stretches that use exactly k different characters. About 14 minutes.

When the rule won't fit a window

A sliding window needs a rule that stays true when you shrink the window. "At most k kinds" does: remove a character and you still have at most k. "Exactly k" doesn't: shrinking can drop you to k − 1.

So don't count "exactly" directly. Can you build it from two counts that a window can handle? Think of it like working out how many people are exactly 30 from how many are at most 30 and at most 29.

Try this: the answer as a difference of two easier counts.

s = "pqpqs", k = 2 · exactly 2 = at most 2 − at most 1

leftright

at most 2: 10

Count windows with at most 2 kinds. With right at 3, every start from 0 to 3 works: 4 windows end here. Totals so far: 1 + 2 + 3 + 4 = 10.

Move 1 of 4

Quick check

Stretches with exactly 2 kinds are the stretches with at most 2 kinds, minus…

Athose with at most 1 kind
Bthose with at most 3 kinds
Cevery stretch

Show the answer

those with at most 1 kind. Taking away the ones with 0 or 1 kinds leaves exactly 2.

Your problem

Exactly k kinds

Count the non-empty runs of consecutive characters that contain exactly k different characters.

Example

s = "pqpqs", k = 2 → 7

0 ≤ length ≤ 100,000 · 1 ≤ k ≤ 26 · only a to z · return a long

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.