Sliding Window Technique - Part 4

Same idea here as the other sliding window problems, except that despite the window being the size "k", we still need to keep track of the 26 letters, making the overall time complexity not O(kn), but rather O(26n), with constant space. Code is down below, cheers, ACC.

Find K-Length Substrings With No Repeated Characters - LeetCode

1100. Find K-Length Substrings With No Repeated Characters

Medium

Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.

 

Example 1:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

Example 2:

Input: s = "home", k = 5
Output: 0
Explanation: Notice k can be larger than the length of s. In this case, it is not possible to find any substring.

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.
• 1 <= k <= 104

Accepted

22,605

Submissions

30,957

public int NumKLenSubstrNoRepeats(string s, int k)
{
    int[] window = new int[26];

    int retVal = 0;
    for (int i = 0; i < s.Length; i++)
    {
        window[(int)(s[i] - 'a')]++;
        if (i == k - 1)
        {
            if (NoRepeats(window)) retVal++;
        }
        else if (i >= k)
        {
            window[(int)(s[i - k] - 'a')]--;
            if (NoRepeats(window)) retVal++;
        }
    }

    return retVal;
}

private bool NoRepeats(int[] window)
{
    for (int i = 0; i < window.Length; i++)
    {
        if (window[i] > 1) return false;
    }
    return true;
}