Substring Count
Filed under Amazon
Free read 1 of 3Use a sliding window of size K to maintain a frequency map of characters currently in the window.
The question
Given a string S and an integer K, count the number of substrings of length K that contain exactly K-1 distinct characters.
Constraints
- 1 <= K <= S.length
- S contains only lowercase English letters
Examples
- Input
- abcba, K=3
- Output
- 2
- Why
- Substrings are 'abc' (3 distinct), 'bcb' (2 distinct), 'cba' (3 distinct). Only 'bcb' works.
Approach
Use a sliding window of size K to maintain a frequency map of characters currently in the window.
Update the count of distinct characters as the window slides by adding the new character and removing the old one.
If the number of keys in the frequency map equals K-1, increment the result counter.
Tips
- What they are testing: Check cases where K=1 (always 0 distinct) and K=length of string.
- Common mistake: Recomputing the distinct character count from scratch for every window, leading to O(N*K) complexity.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.