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) —
推荐阅读:吃水果的禁忌以及富含维生素的水果 黄瓜的营养价值保健效果及食用方法 土鸡蛋与洋鸡蛋的营养价值以及区别 冬季适当吃糯米类食物有御寒滋补之功效 三类护耳食物可以延缓老年人听力下降 红枣养生知识:食用红枣需注意的问题 健康面点拒绝这些有毒的添加剂原料 火锅健康吃法:先素后荤 煮烫适度 少吃辣 柚子的保健功效以及食用柚子的禁忌 许多人已经走入了补充益生菌的误区
- 评论列表
-
- 添加评论