Two Pointer and Sliding Window Algorithm to Find K-Length Substr

  • 时间:2020-09-20 13:49:13
  • 分类:网络文摘
  • 阅读:86 次

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) —

推荐阅读:
神秘的海底探索机器人|小学作文  秋之韵|小学作文  新年的颜色|小学作文  我也是偶然成为你的姐姐|小学作文  生命是什么?|小学作文  伟大的创造——迪卡尔的故事  迪卡尔受教会迫害致死  一个直角三角形里画一个最大的正方形  非凡的天才——伽罗华  承受磨炼——伽罗华 
评论列表
添加评论