Standard Bar Strings · Medium O(n) · O(k)
A spectrum monitor logs a day's broadcast as one long string where each character names the channel a transmitter occupied. Planning needs to know how many contiguous listening windows used exactly K distinct channels — windows are counted by position, so identical content at different offsets counts separately. The monitor answers by counting windows with at most K channels, counting those with at most K-1, and taking the difference.
Input: A string S of lowercase English letters and an integer K.
Output: The number of (not necessarily distinct) substrings of S that contain exactly K distinct characters.
1 <= S.length <= 10^51 <= K <= 26Input: {"S":"aba","K":2}
Output: 3
"ab", "ba" and "aba" each mix exactly two channels.
Input: {"S":"abaaca","K":1}
Output: 7
Six single-character windows plus the "aa" pair — every window with one distinct channel.