Distinct-Letter Windows
EasySliding Window
Problem
A password generator wants to reuse chunks of a lowercase seed string s, but only chunks of exactly k characters in which no letter repeats.
Return how many windows of length k in s have all distinct letters. Windows at different start positions count separately even if their text is the same.
Example 1
- Input:
- s = "xyzzaz", k = 3
- Output:
- 1
The windows are "xyz", "yzz", "zza", "zaz". Only "xyz" has no repeated letter.
Example 2
- Input:
- s = "abcab", k = 2
- Output:
- 4
"ab", "bc", "ca", "ab": all four are fine.
Constraints
- 1 ≤ s.length ≤ 10^5
- 1 ≤ k ≤ 10^5
- s contains only lowercase English letters.
Hint
Show the first hint
Checking each window with a fresh set costs O(k) per window. What changes as the window slides?
Walkthrough
How to approach it
01Clarify before coding
- What if k is larger than s? No window exists, answer 0.
- Do identical windows at different positions count twice? Yes.
- Can k exceed 26? It can, but then a repeat is guaranteed, so the answer is 0.
02Brute force
For each start i, build a set from s[i..i+k-1] and check its size equals k.
Cost: O(n·k) time; up to 26 effective letters keeps it from exploding, but it still redoes almost all work per window.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.