Problem Explanation

The problem asks to find the number of substrings of a given length (K) with distinct characters from a given string (S).

Lets consider the below example:

Example 1:

for S = "havefunonleetcode", K = 5

We need to find substrings of length 5, which have all distinct characters. The substrings that meet the criteria are 'havef', 'avefu', 'vefun', 'efuno', 'etcod', 'tcode'. Therefore, the output is 6.

Solution Approach

The solution uses a sliding window approach and an array to keep track of the frequency of characters. We keep sliding the window of size K over the string and we keep track of the frequency of the characters in the window. If all the characters in the window are distinct, we increment the answer by 1. The frequency of the characters is achieved by using the count array.

Let's illustrate this with the example of S = "havefunonleetcode", K = 5.

1. First, we initialize a frequency counter with 26 zeros (to represent the 26 English lower case letters).
2. We start reading the string from the left, for every character we meet, we update the frequency counter.
3. When we reach the Kth character, we check if all frequencies are 1 (which means no repeated characters). If so, we increment the answer counter.
4. Now we slide the window to right, which means we decrement the frequency of the first character in the previous window (as it is no longer in the current window), and include the next character.
5. Repeat the above two steps until we reach the end of the string.

Solution in Python

1
2python
3class Solution:
4    def numKLenSubstrNoRepeats(self, S: str, K: int) -> int:
5        count = [0] * 26
6        res = 0
7        for i in range(len(S)):
8            count[ord(S[i]) - ord('a')] += 1
9            if i >= K:
10                count[ord(S[i - K]) - ord('a')] -= 1
11            if i >= K - 1 and len(set(count)) == 2:
12                res += 1
13        return res

Solution in Java

1
2java
3class Solution {
4    public int numKLenSubstrNoRepeats(String S, int K) {
5        if(K > S.length()) return 0;
6
7        int[] map=new int[128];
8        char[] sc=S.toCharArray();
9        int res=0;
10        for(int i =0;i<K;i++)
11            map[sc[i]]++;
12        
13        if(helper(map)==K)
14            res++;
15        
16        for(int i=K;i<sc.length;i++) {
17            map[sc[i]]++;
18            map[sc[i-K]]--;
19            
20            if(helper(map)==K)
21                res++;
22        }
23        return res;
24    }
25    
26    private int helper(int[] map) {
27        int cnt=0;
28        for(int v : map) {
29            if(v != 0)
30                cnt+=v;
31        }
32        return cnt;
33    }
34}

Solution in Javascript

1
2javascript
3/**
4 * @param {string} S
5 * @param {number} K
6 * @return {number}
7 */
8var numKLenSubstrNoRepeats = function(S, K) {
9    const count = new Array(256).fill(0);
10    let res = 0;
11
12    for (let i = 0; i < S.length; i++) {
13        ++count[S.charCodeAt(i)];
14        if (i >= K) --count[S.charCodeAt(i - K)];
15        if (i >= K - 1 && Math.max(...count) === 1) res++;
16    } 
17    return res;
18};

Solution in C++

1
2cpp
3class Solution {
4public:
5    int numKLenSubstrNoRepeats(string S, int K) {
6        int ans = 0;
7        int unique = 0;
8        vector<int> count(26); 
9
10        for (int i = 0; i < S.length(); ++i) {
11            if (++count[S[i] - 'a'] == 1)
12                ++unique;
13            if (i >= K && --count[S[i - K] - 'a'] == 0)
14                --unique;
15            if (unique == K)
16                ++ans;
17        }
18        return ans;
19    }
20};

Solution in C#

1
2csharp
3public class Solution {
4    public int NumKLenSubstrNoRepeats(string S, int K) {
5        int[] count = new int[26];
6        int res = 0;
7        for(int i = 0; i < S.Length; i++)
8        {
9            count[S[i] - 'a'] += 1;
10            if (i >= K)
11                count[S[i - K] - 'a'] -= 1;
12            if (i >= K - 1 && count.Max() == 1) 
13                res += 1;
14        }
15        return res;
16    }
17}

Please focus on the fact that this solution utilizes a sliding window technique and counts the frequency of characters in the window. At every step, if all the characters in the window are distinct, we increment the answer.The main challenge is to keep track of the frequency of each character in your sliding window. This is where your frequency array (for Python), map (for Java), count array (for JavaScript, C++ & C#) comes into play.

This question is a typical sliding window problem. If you understand how sliding window works, you will be able to understand the solution easily. A sliding window is a sub-list that runs over an underlying collection. This window could either be a sub-array or a sub-string or any data structure that you've decided to use.

In the problem above, we slide our window across the string and keep track of the frequency of the characters in our window.

In conclusion, these solutions efficiently solve the problem by using the sliding window approach and counting the occurrences of characters in the sliding window. The solution applies to Python, Java, Javascript, C++, and C#. It has a time complexity of O(n), where n is the length of the string, and a space complexity of O(1), ignoring the space required for the output. This is the most optimal and efficient solution for this problem, as we only pass through the string 'S' once.

Remember practice is key to mastering sliding window problems. The more problems you solve, the more familiar you will become with this concept which will allow you to come up with solutions quicker and with ease.