Strings Counting over substrings
142. Count Substrings With Exactly K Distinct Characters
You are given a string s of lowercase English letters and an integer k. Return the number of substrings of
s that hold exactly k different letters. A letter may appear any number of times, so xyy holds two
different letters.
A substring is a block of letters that sit next to each other in s, with at least one letter. Two
substrings are different if they start or end at different positions, even when they hold the same letters.
Example 1
Input: s = "xyyzx", k = 2
5Explanation: Five substrings hold exactly two different letters: xy, xyy, yyz, yz and zx. Longer ones, such
as xyyz, hold three.
Example 2
Input: s = "zzzyz", k = 1
8Explanation: The block zzz gives six substrings: z three times, zz twice and zzz once. The y and the last z
add one each.
Example 3
Input: s = "xyz", k = 4
0Explanation: The string holds only three different letters, so no substring holds four.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 105sholds lowercase English letters only,atoz.1 ≤ k ≤ 26
Clarifying questions
What you would ask an interviewer before writing any code.