โ† Amazon questions

Substring Count

Filed under Amazon

Free read 1 of 3

Use 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

  1. Use a sliding window of size K to maintain a frequency map of characters currently in the window.

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.