# Count number of substrings with exactly k distinct characters

[Question]: You are given a string ‘str’ of lowercase alphabets and an integer’k’ .
Your task is to return the count all the possible substrings that have exactly ‘k’ distinct characters.
For example:
‘str’ = abcad and ‘k’ = 2.
We can see that the substrings {ab, bc, ca, ad} are the only substrings with 2 distinct characters. Therefore, the answer will be 4.
Example 2:
Input ABCDEFGHIJ
Output 6

``````// Question: count with k diffrent charcters.
// TC: O(nXn)
// SC: O(1) Only 26 size array is used, which can be considered constant space.

func most_k_chars(_ s: String, _ k: Int) -> Int {
if s.isEmpty { return 0 }
var map:[Character:Int] = [:]
var num = 0, left = 0

for char in s.indices {
map[s[char], default:0] += 1

while map.count > k {
let leftIndex = s[s.index(s.startIndex, offsetBy: left)]
map[leftIndex, default:0] -= 1
if map[leftIndex] == 0 {
map[leftIndex] = nil
}
left+=1
}

if let i = s.firstIndex(of: s[char]) {
let indexEl: Int = s.distance(from: s.startIndex, to: i)
num += indexEl - left + 1
}
}
return num
}

func exact_k_chars(_ s: String, _ k: Int) -> Int {
return most_k_chars(s, k) - most_k_chars(s, k - 1)
}

var s1 = "abcdefghij"
var k1 = 5
print("Total substrings with exactly ", k1 , " distinct characters : " ,exact_k_chars(s1, k1))// 6
``````