Find K-Length Substrings With No Repeated Characters

medium sliding window hash map string

Problem

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

Inputs = "havefunonleetcode", k = 5

Output6

The 6 valid windows are "havef", "avefu", "vefun", "efuno", "etcod", "tcode" — each has 5 distinct characters.

s (string)

def num_k_len_substr_no_repeats(s, k):
    if k > len(s):
        return 0
    count = 0
    freq = {}
    for i, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1
        if i >= k:
            left = s[i - k]
            freq[left] -= 1
            if freq[left] == 0:
                del freq[left]
        if i >= k - 1 and len(freq) == k:
            count += 1
    return count

function numKLenSubstrNoRepeats(s, k) {
  if (k > s.length) return 0;
  let count = 0;
  const freq = new Map();
  for (let i = 0; i < s.length; i++) {
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
    if (i >= k) {
      const left = s[i - k];
      freq.set(left, freq.get(left) - 1);
      if (freq.get(left) === 0) freq.delete(left);
    }
    if (i >= k - 1 && freq.size === k) count++;
  }
  return count;
}

class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        if (k > s.length()) return 0;
        int count = 0;
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freq.merge(c, 1, Integer::sum);
            if (i >= k) {
                char left = s.charAt(i - k);
                if (freq.merge(left, -1, Integer::sum) == 0) freq.remove(left);
            }
            if (i >= k - 1 && freq.size() == k) count++;
        }
        return count;
    }
}

int numKLenSubstrNoRepeats(string s, int k) {
    if (k > (int)s.size()) return 0;
    int count = 0;
    unordered_map<char, int> freq;
    for (int i = 0; i < (int)s.size(); i++) {
        freq[s[i]]++;
        if (i >= k) {
            char left = s[i - k];
            if (--freq[left] == 0) freq.erase(left);
        }
        if (i >= k - 1 && (int)freq.size() == k) count++;
    }
    return count;
}

Explanation

We want to count windows of length exactly k where all characters are different. A window of k characters has no repeats precisely when it contains k distinct characters, so we just keep a frequency map and watch how many distinct keys it holds.

As we move the right edge to index i, we add s[i] to freq. Once the window grows past size k (when i >= k), we drop the character that left on the left, s[i - k], and delete its key if its count hits zero. This keeps the window exactly k wide.

Whenever the window is full (i >= k - 1) and the number of map keys equals k, every character inside is unique, so we increment count.

Example: s = "havefunonleetcode", k = 5. Windows like "havef" and "avefu" each hold 5 distinct letters and count, while a window containing a repeat (fewer than 5 keys) is skipped. The total here is 6.

Each character is added and removed at most once, so the whole count is a single linear scan.

Time: O(n) Space: O(k)