1100

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

Companies:
Amazon

Related Topics:
Hash Table, String, Sliding Window

Solution 1. Fixed-length Sliding Window

// OJ: https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/
// Author: github.com/lzl124631x
// 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;
    }
};