Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1100.html

1100. Find K-Length Substrings With No Repeated Characters

Level

Medium

Description

Given a string S, return the number of substrings 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 is not possible to find any substring.

Note:

  1. 1 <= S.length <= 10^4
  2. All characters of S are lowercase English letters.
  3. 1 <= K <= 10^4

Solution

If S has length less than K, then it is not possible to find any substring, so return 0.

Use a map to store each character and its number of occurrences in each substring. Initially, add the first K characters of S to the map together with their numbers of occurrences. Each time a new substring is met, decrease the number of occurrences of the first character in the previous substring by 1 and increase the number of occurrences of the last character in the current substring by 1. If a character’s number of occurrences becomes 0, remove the character from the map. For each substring (including the first substring), the substring doesn’t contain repeated characters if and only if the map contains exactly K keys. In this way, the number of substrings of length K with no repeated characters can be calculated.

  • class Solution {
    public int numKLenSubstrNoRepeats(String S, int K) {
        if (S == null || S.length() < K)
            return 0;
        int length = S.length();
        Map<Character, Integer> letterCountMap = new HashMap<Character, Integer>();
        for (int i = 0; i < K; i++) {
            char c = S.charAt(i);
            int count = letterCountMap.getOrDefault(c, 0);
            count++;
            letterCountMap.put(c, count);
        }
        int substringsCount = 0;
        if (letterCountMap.keySet().size() == K)
            substringsCount++;
        for (int i = K; i < length; i++) {
            char prevC = S.charAt(i - K);
            char curC = S.charAt(i);
            int prevCount = letterCountMap.getOrDefault(prevC, 0);
            prevCount--;
            if (prevCount == 0)
                letterCountMap.remove(prevC);
            else
                letterCountMap.put(prevC, prevCount);
            int curCount = letterCountMap.getOrDefault(curC, 0);
            curCount++;
            letterCountMap.put(curC, curCount);
            if (letterCountMap.keySet().size() == K)
                substringsCount++;
        }
        return substringsCount;
    }
}

  • // OJ: https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        int N = s.size(), ans = 0, cnt[26] = {}, unique = 0;
        for (int i = 0; i < N; ++i) {
            if (++cnt[s[i] - 'a'] == 1) ++unique;
            if (i - k >= 0 && --cnt[s[i - k] - 'a'] == 0) --unique;
            ans += unique == k;
        }
        return ans;
    }
};

  • class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        ans = j = 0
        mp = {}
        for i, c in enumerate(s):
            if c in mp:
                j = max(j, mp[c] + 1)
            mp[c] = i
            if i - j + 1 >= k:
                ans += 1
        return ans



  • func numKLenSubstrNoRepeats(s string, k int) (ans int) {
	if k > len(s) || k > 26 {
		return 0
	}
	cnt := [128]int{}
	for i, j := 0, 0; i < len(s); i++ {
		cnt[s[i]]++
		for cnt[s[i]] > 1 || i-j+1 > k {
			cnt[s[j]]--
			j++
		}
		if i-j+1 == k {
			ans++
		}
	}
	return
}

All Problems

All Solutions