Sliding Window
好题：
Minimum Window Substring
Longest substring without repeating characters
模板
maintain a window = [begin, end] -> s.substring(begin, end +1)
define what is a valid window
move end pointer one step forward per iteration
only move begin pointer when found a valid window
for (int end = 0; end < s.length(); end++) {
//proceed s.charAt(end)
while window is still valid {
//update res
//move begin pointer
}
}找最小window: while window is still valid
找最大window: while window is still invalid
为什么不用begin作iterator?
因为如果iterator begin pointer的话最后both begin and end need to move to the end, which means each char has been visited by exact 2 times.
while if we iterate end pointer to the end, each char has been visited by at most 2 times(only when char is part of a valid window)
Minimum Window Substring
sliding window模板题，多练
move end pointer one step forward per iteration
only move begin pointer when found a valid window
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
return "";
}
Map<Character, Integer> dict = new HashMap<>();
for (char c : t.toCharArray()) {
dict.put(c, dict.getOrDefault(c, 0) + 1);
}
int counter = 0;
String res = s + t;
int begin = 0;
for (int end = 0; end < s.length(); end++) {
//proceed s.charAt(end)
char cur = s.charAt(end);
Integer cnt = dict.get(cur);
if (cnt != null) {
dict.put(cur, cnt - 1);
if (dict.get(cur) == 0) {
counter++;
}
}
//while cur window is still a valid window
while (counter == dict.size()) {
//update res
res = end - begin + 1 < res.length() ? s.substring(begin, end + 1) : res;
//move begin
char prev = s.charAt(begin);
Integer count = dict.get(prev);
if (count != null) {
dict.put(prev, count + 1);
if (dict.get(prev) == 1) {
counter--;
}
}
begin++;
}
}
return res.length() == s.length() + t.length() ? "" : res;
}Find All Anagrams in a string
sliding window end pointer模板
class Solution {
/*
**window [begin, end] -> s.substring(begin, end + 1)
**valid window is an anagram of string p
convert String p to a dict, char->freq
move end pointer one step forward per iteration-> for loop
deal with s.charAt(end)
while window is valid {
update res
deal with s.charAt(begin) before moving begin pointer one step forward
}
*/
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
//validate input
if (s == null || s.length() < p.length()) {
return res;
}
//convert to a map, char->cnt
Map<Character, Integer> charToCnt = new HashMap<>();
for (char c : p.toCharArray()) {
charToCnt.put(c, charToCnt.getOrDefault(c, 0) + 1);
}
int counter = 0;
int begin = 0;
//move end pointer one step forward per iteration
for (int end = 0; end < s.length(); end++) {
char cur = s.charAt(end);
Integer cnt = charToCnt.get(cur);
//decrement cnt if charToCnt contains cur
if (cnt != null) {
charToCnt.put(cur, cnt - 1);
if (charToCnt.get(cur) == 0) {
counter++;
}
}
//while window is valid
while (counter == charToCnt.size()) {
//update res
if (end - begin + 1 == p.length()) {
res.add(begin);
}
//move begin
char c = s.charAt(begin);
Integer count = charToCnt.get(c);
if (count != null) {
charToCnt.put(c, count + 1);
if (charToCnt.get(c) == 1) {
counter--;
}
}
begin++;
}
}
return res;
}
}Longest substring without repeating characters
find max window的模板题
重点在于how to define a valid window
while window is invalid
class Solution {
/*
maintain a window[begin, end] ->consist of all unique char
create a map to store all char in the window, char-> cnt
valid window -> no dup char
move end pointer one step forward per iteration
increment cnt of cur char in the map
window is invalid -> map.get(cur) > 1
while window is invalid {
//move begin pointer
}
update res for a valid window
*/
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Map<Character, Integer> charToCnt = new HashMap<>();
int begin = 0;
int len = 0;
for (int end = 0; end < s.length(); end++) {
char cur = s.charAt(end);
charToCnt.put(cur, charToCnt.getOrDefault(cur, 0) + 1);
//while window is invalid
while (charToCnt.get(cur) > 1) {
//move begin pointer
char c = s.charAt(begin);
charToCnt.put(c, charToCnt.get(c) - 1);
begin++;
}
//update res
len = Math.max(len, end - begin + 1);
}
return len;
}
}组合题，一个思路
class Solution {
/*
window[begin, end]
maintain a hashmap to store all char in the window, char->cnt
window is valid -> set.size() <=2
for (int end = 0; end < s.length(); end++) {
//add s.charAt(end) to set
while window is invalid{
//move begin pointer
}
//update res when window is valid
}
*/
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s.length() < 3) {
return s.length();
}
int begin = 0;
Map<Character, Integer> charToCnt = new HashMap<>();
int len = 0;
for (int end = 0; end < s.length(); end++) {
char cur = s.charAt(end);
charToCnt.put(cur, charToCnt.getOrDefault(cur, 0) + 1);
//while window is invalid
while (charToCnt.size() > 2) {
//move begin
char c = s.charAt(begin);
int cnt = charToCnt.get(c);
charToCnt.put(c, cnt - 1);
if (charToCnt.get(c) == 0) {
charToCnt.remove(c);
}
begin++;
}
//update res
len = Math.max(len, end - begin + 1);
}
return len;
}
}和上一题的区别只是把2改成K
从题目上看以为还是sliding window的思路，实际上是divide & conquer
先cnt所有char ,然后顺序遍历a~z, 如果cnt[i] == 0, skip to next char.
if cnt[i] < k,说明最终返回的结果里肯定没有这个char,所以就遍历string找到这个char,然后recursive call s.substring(0, i) 和substring(i + 1),在返回的left和right中返回大的
class Solution {
public int longestSubstring(String s, int k) {
if (s == null || s.length() < k) {
return 0;
}
if ( k < 2) return s.length();
return helper(s.toCharArray(), 0, s.length(), k);
}
private int helper(char[] arr, int start, int end, int k) {
if (end - start < k) return 0;
int[] counts = new int[26];
for (int i = start; i < end; i++) {
counts[arr[i] - 'a']++;
}
boolean valid = true;
for (int i = 0; i < 26; i++) {
if (counts[i] > 0 && counts[i] < k) {
valid = false;
break;
}
}
if (valid) {
return end - start;
}
int res = 0, newStart = start;
for (int i = start; i < end; i++) {
if (counts[arr[i] - 'a'] < k) {
res = Math.max(res, helper(arr,newStart, i, k));
newStart = i + 1;
}
}
res = Math.max(res, helper(arr,newStart, end, k));
return res;
}
}简单修改下sliding window模板
每次先
sum += nums[end], 然后checksum >= s的情况下, 再sum -= nums[begin++];Time: O(N), Space: O(1)
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;
int N = nums.length;
int sum = 0, size = N + 1;
int begin = 0, end = 0;
while (end < N) {
sum += nums[end];
while (sum >= s) {
size = Math.min(size, end - begin + 1);
sum -= nums[begin];
begin++;
}
end++;
}
return size == N + 1 ? 0 : size;
}这题最直接的是用HashMap,O(N)& O(N),打败了67.39%
还可以用sliding window的思路解题设一个cur指针
建一个HashSet
当cur > k的时候，每次先删除nums[cur - k - 1]
再判断set.add(nums[cur])是否为false,从而判断是否contain duplicate within at most K distance,打败了97%
public boolean containsNearbyDuplicate(int[] nums, int k) {
//hashset and sliding window
if(nums == null || nums.length < 2) return false;
Set<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++){
if(i > k){
set.remove(nums[i - k - 1]);
}
if(!set.add(nums[i])) return true;
}
return false;
}Last updated
Was this helpful?