1100. Find K-Length Substrings With No Repeated Characters 🔒

Description

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

Solutions

Solution 1: Sliding Window + Hash Table

Thinking

Checking every substring of length \(k\) for uniqueness costs \(O(nk)\). With \(n,k\le 10^4\) this can pass, yet adjacent windows differ by only one character entering and one leaving.

Maintain a window of length \(k\) and a frequency map: add \(s[i]\), drop \(s[i-k]\), and remove a key when its count hits zero. The map has exactly \(k\) keys if and only if every character in the window appears once, so that test increments the answer.

We maintain a sliding window of length \(k\), and use a hash table \(cnt\) to count the occurrences of each character in the window.

First, we add the first \(k\) characters of the string \(s\) to the hash table \(cnt\), and check whether the size of \(cnt\) is equal to \(k\). If it is, it means that all characters in the window are different, and the answer \(ans\) is incremented by one.

Next, we start to traverse the string \(s\) from \(k\). Each time we add \(s[i]\) to the hash table \(cnt\), and at the same time subtract \(s[i-k]\) from the hash table \(cnt\) by one. If \(cnt[s[i-k]]\) is equal to \(0\) after subtraction, we remove \(s[i-k]\) from the hash table \(cnt\). If the size of the hash table \(cnt\) is equal to \(k\) at this time, it means that all characters in the window are different, and the answer \(ans\) is incremented by one.

Finally, return the answer \(ans\).

The time complexity is \(O(n)\), and the space complexity is \(O(\min(k, |\Sigma|))\), where \(n\) is the length of the string \(s\); and \(\Sigma\) is the character set, in this problem the character set is lowercase English letters, so \(|\Sigma| = 26\).

Python3JavaC++GoTypeScriptPHP

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        cnt = Counter(s[:k])
        ans = int(len(cnt) == k)
        for i in range(k, len(s)):
            cnt[s[i]] += 1
            cnt[s[i - k]] -= 1
            if cnt[s[i - k]] == 0:
                cnt.pop(s[i - k])
            ans += int(len(cnt) == k)
        return ans

class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        int n = s.length();
        if (n < k) {
            return 0;
        }
        Map<Character, Integer> cnt = new HashMap<>(k);
        for (int i = 0; i < k; ++i) {
            cnt.merge(s.charAt(i), 1, Integer::sum);
        }
        int ans = cnt.size() == k ? 1 : 0;
        for (int i = k; i < n; ++i) {
            cnt.merge(s.charAt(i), 1, Integer::sum);
            if (cnt.merge(s.charAt(i - k), -1, Integer::sum) == 0) {
                cnt.remove(s.charAt(i - k));
            }
            ans += cnt.size() == k ? 1 : 0;
        }
        return ans;
    }
}

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        int n = s.size();
        if (n < k) {
            return 0;
        }
        unordered_map<char, int> cnt;
        for (int i = 0; i < k; ++i) {
            ++cnt[s[i]];
        }
        int ans = cnt.size() == k;
        for (int i = k; i < n; ++i) {
            ++cnt[s[i]];
            if (--cnt[s[i - k]] == 0) {
                cnt.erase(s[i - k]);
            }
            ans += cnt.size() == k;
        }
        return ans;
    }
};

func numKLenSubstrNoRepeats(s string, k int) (ans int) {
    n := len(s)
    if n < k {
        return
    }
    cnt := map[byte]int{}
    for i := 0; i < k; i++ {
        cnt[s[i]]++
    }
    if len(cnt) == k {
        ans++
    }
    for i := k; i < n; i++ {
        cnt[s[i]]++
        cnt[s[i-k]]--
        if cnt[s[i-k]] == 0 {
            delete(cnt, s[i-k])
        }
        if len(cnt) == k {
            ans++
        }
    }
    return
}

function numKLenSubstrNoRepeats(s: string, k: number): number {
    const n = s.length;
    if (n < k) {
        return 0;
    }
    const cnt: Map<string, number> = new Map();
    for (let i = 0; i < k; ++i) {
        cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
    }
    let ans = cnt.size === k ? 1 : 0;
    for (let i = k; i < n; ++i) {
        cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
        cnt.set(s[i - k], (cnt.get(s[i - k]) ?? 0) - 1);
        if (cnt.get(s[i - k]) === 0) {
            cnt.delete(s[i - k]);
        }
        ans += cnt.size === k ? 1 : 0;
    }
    return ans;
}

class Solution {
    /**
     * @param String $s
     * @param Integer $k
     * @return Integer
     */
    function numKLenSubstrNoRepeats($s, $k) {
        $n = strlen($s);
        if ($n < $k) {
            return 0;
        }
        $cnt = [];
        for ($i = 0; $i < $k; ++$i) {
            if (!isset($cnt[$s[$i]])) {
                $cnt[$s[$i]] = 1;
            } else {
                $cnt[$s[$i]]++;
            }
        }
        $ans = count($cnt) == $k ? 1 : 0;
        for ($i = $k; $i < $n; ++$i) {
            if (!isset($cnt[$s[$i]])) {
                $cnt[$s[$i]] = 1;
            } else {
                $cnt[$s[$i]]++;
            }
            if ($cnt[$s[$i - $k]] - 1 == 0) {
                unset($cnt[$s[$i - $k]]);
            } else {
                $cnt[$s[$i - $k]]--;
            }
            $ans += count($cnt) == $k ? 1 : 0;
        }
        return $ans;
    }
}

1100. Find K-Length Substrings With No Repeated Characters 🔒

Description

Solutions

Solution 1: Sliding Window + Hash Table

Comments