Two Pointer and Sliding Window Algorithm to Find K-Length Substrings With No Repeated Characters

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 <= S.length <= 10^4
All characters of S are lowercase English letters.
1 <= K <= 10^4

Sliding Window to Find K-Length Substrings With No Repeated Characters

Since all the input are lowercase letters, we can use a static array of size 26 to record the character frequencies. Then, we can easily define a check function that will tell us if there are duplicate letters.

Then, we can initialise the counter array with the first K letters, then starting from K index, at each iteration, we decrement the left-most character’s counter, and increment the current character’s counter. And, we can increment the answer if there are no duplicate letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int numKLenSubstrNoRepeats(string S, int K) {
        if (S.size() < K) return 0;
        int count[26];
        std::fill(begin(count), end(count), 0);
        for (int i = 0; i < K; ++ i) {
            count[S[i] - 97] ++;
        }
        int ans = check(count) ? 1 : 0;
        for (int i = K; i < S.size(); ++ i) {
            count[S[i - K] - 97] --; // left-most letter
            count[S[i] - 97] ++;     // current letter
            if (check(count)) {
                ans ++;
            }
        }
        return ans;
    }
private:
    bool check(int count[26]) { // O(1)
        for (int i = 0; i < 26; ++ i) {
            if (count[i] > 1) return false;
        }
        return true;
    }
};

class Solution {
public:
    int numKLenSubstrNoRepeats(string S, int K) {
        if (S.size() < K) return 0;
        int count[26];
        std::fill(begin(count), end(count), 0);
        for (int i = 0; i < K; ++ i) {
            count[S[i] - 97] ++;
        }
        int ans = check(count) ? 1 : 0;
        for (int i = K; i < S.size(); ++ i) {
            count[S[i - K] - 97] --; // left-most letter
            count[S[i] - 97] ++;     // current letter
            if (check(count)) {
                ans ++;
            }
        }
        return ans;
    }
private:
    bool check(int count[26]) { // O(1)
        for (int i = 0; i < 26; ++ i) {
            if (count[i] > 1) return false;
        }
        return true;
    }
};

The time complexity for above C++ code is O(N) where N is the number of characters in S, and the space complexity is O(1).

Finding K-Length Substrings using Two Pointer, Sliding Window and Set

We can use a set to record the unique letters in the current sliding window. And we have two indices pointing to the left and right margin of the sliding window. If S[j] is duplicate in the set, we continue removing the S[i] – and increment i. We then add S[j] to the set, and if the distance between i and j is larger than K, we increment the answer.

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

class Solution {
public:
    int numKLenSubstrNoRepeats(string S, int K) {
        if (S.size() < K) return 0;
        int ans = 0;
        unordered_set<char> data;
        int i = 0;
        for (int j = 0; j < S.size(); ++ j) {
            while (data.count(S[j])) {
                data.erase(S[i ++]);
            }
            data.insert(S[j]);
            if (j - i + 1 >= K) {
                ans ++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int numKLenSubstrNoRepeats(string S, int K) {
        if (S.size() < K) return 0;
        int ans = 0;
        unordered_set<char> data;
        int i = 0;
        for (int j = 0; j < S.size(); ++ j) {
            while (data.count(S[j])) {
                data.erase(S[i ++]);
            }
            data.insert(S[j]);
            if (j - i + 1 >= K) {
                ans ++;
            }
        }
        return ans;
    }
};

If there duplicate letters in the sliding window, we have to slide right until there are not. The complexity is O(N) in terms of both space and time.

–EOF (The Ultimate Computing & Technology Blog) —