Problem

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

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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 <= 10^4
  • s consists of lowercase English letters.
  • 1 <= k <= 10^4

Solution

Method 1 – Sliding Window with HashSet

Intuition

We want to count all substrings of length k in s that have no repeated characters. A sliding window of size k with a set to track unique characters allows us to efficiently check each substring.

Approach

  1. If k > len(s), return 0 immediately.
  2. Use a sliding window of size k and a set to track unique characters in the window.
  3. For each window, if all characters are unique (set size == k), increment the answer.
  4. Slide the window by removing the leftmost character and adding the next character.
  5. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        if (k > s.size()) return 0;
        unordered_map<char, int> cnt;
        int ans = 0, left = 0;
        for (int right = 0; right < s.size(); ++right) {
            cnt[s[right]]++;
            if (right - left + 1 > k) {
                if (--cnt[s[left]] == 0) cnt.erase(s[left]);
                left++;
            }
            if (right - left + 1 == k && cnt.size() == k) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func numKLenSubstrNoRepeats(s string, k int) int {
    if k > len(s) {
        return 0
    }
    cnt := make(map[byte]int)
    ans, left := 0, 0
    for right := 0; right < len(s); right++ {
        cnt[s[right]]++
        if right-left+1 > k {
            cnt[s[left]]--
            if cnt[s[left]] == 0 {
                delete(cnt, s[left])
            }
            left++
        }
        if right-left+1 == k && len(cnt) == k {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        if (k > s.length()) return 0;
        Map<Character, Integer> cnt = new HashMap<>();
        int ans = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            cnt.put(s.charAt(right), cnt.getOrDefault(s.charAt(right), 0) + 1);
            if (right - left + 1 > k) {
                char c = s.charAt(left);
                cnt.put(c, cnt.get(c) - 1);
                if (cnt.get(c) == 0) cnt.remove(c);
                left++;
            }
            if (right - left + 1 == k && cnt.size() == k) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun numKLenSubstrNoRepeats(s: String, k: Int): Int {
        if (k > s.length) return 0
        val cnt = mutableMapOf<Char, Int>()
        var ans = 0
        var left = 0
        for (right in s.indices) {
            cnt[s[right]] = cnt.getOrDefault(s[right], 0) + 1
            if (right - left + 1 > k) {
                val c = s[left]
                cnt[c] = cnt[c]!! - 1
                if (cnt[c] == 0) cnt.remove(c)
                left++
            }
            if (right - left + 1 == k && cnt.size == k) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        if k > len(s):
            return 0
        cnt = {}
        ans = left = 0
        for right, c in enumerate(s):
            cnt[c] = cnt.get(c, 0) + 1
            if right - left + 1 > k:
                cnt[s[left]] -= 1
                if cnt[s[left]] == 0:
                    del cnt[s[left]]
                left += 1
            if right - left + 1 == k and len(cnt) == k:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn num_k_len_substr_no_repeats(s: String, k: i32) -> i32 {
        let s = s.as_bytes();
        let k = k as usize;
        if k > s.len() { return 0; }
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        let (mut ans, mut left) = (0, 0);
        for right in 0..s.len() {
            *cnt.entry(s[right]).or_insert(0) += 1;
            if right + 1 - left > k {
                let e = cnt.entry(s[left]).or_insert(0);
                *e -= 1;
                if *e == 0 { cnt.remove(&s[left]); }
                left += 1;
            }
            if right + 1 - left == k && cnt.len() == k {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    numKLenSubstrNoRepeats(s: string, k: number): number {
        if (k > s.length) return 0;
        const cnt: Record<string, number> = {};
        let ans = 0, left = 0;
        for (let right = 0; right < s.length; right++) {
            cnt[s[right]] = (cnt[s[right]] || 0) + 1;
            if (right - left + 1 > k) {
                cnt[s[left]]--;
                if (cnt[s[left]] === 0) delete cnt[s[left]];
                left++;
            }
            if (right - left + 1 === k && Object.keys(cnt).length === k) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. Each character is processed at most twice.
  • 🧺 Space complexity: O(k), for the sliding window and character count map