about Sliding Window5
Wed, Sep 1, 2021
6-minute read
Sliding Window pattern in algorithm, 滑动窗口套路
Longest Substring With K Typed Characters
**字符串的时候， map 里面，不符合的或者超过边界的左边吐出去的时候， count 加上，
String Frequency In Windows
Given a string containing only 'A', 'B', 'C', 'D', return the number of occurrences of substring which has length 4 and includes all of the characters from 'A', 'B', 'C', 'D' with in descending sorted order.
Assumptions:
The given string is not null and has length of >= 4.
In the output, if two substrings have the same frequency, then they should be sorted by the their natural order.
Examples:
“ABCDABCDD”, --> {"ABCD" : 2, "BCDA" : 1, "CDAB" : 1, "DABC" : 1}
public class Frequency {
* public String str;
* public int freq;
* public Frequency(String str, int freq) {
* this.str = str;
* this.freq = freq;
* }
* }
public class Solution {
public List<Frequency> frequency(String input) {
// Write your solution here.
Map<String, Integer> freqMap = new HashMap<>();
Map<Character, Integer> countMap = new HashMap<>();
countMap.put('A', 1);
countMap.put('B', 1);
countMap.put('C', 1);
countMap.put('D', 1);
int count = 4;
int width = 4;
for(int i = 0; i < input.length(); ++i) {
if(i >= width) {
char removedChar = input.charAt(i - width);
countMap.put(removedChar, countMap.get(removedChar) + 1);
if(countMap.get(removedChar) == 1) {
count++;
}
}
char insertChar = input.charAt(i);
countMap.put(insertChar, countMap.get(insertChar) - 1);
if(countMap.get(insertChar) == 0) {
count--;
}
if(i >= 3 && count == 0) {
String subStr = input.substring(i - 3, i + 1);
freqMap.put(subStr, freqMap.getOrDefault(subStr, 0) + 1);
}
}
List<Map.Entry<String, Integer>> entryList = new ArrayList<>();
for(Map.Entry<String, Integer> entry: freqMap.entrySet()) {
entryList.add(entry);
}
Collections.sort(entryList, new EntryComparator());
List<Frequency> ret = new ArrayList<Frequency>();
for(Map.Entry<String, Integer> entry: entryList) {
ret.add(new Frequency(entry.getKey(), entry.getValue()));
}
return ret;
}
private class EntryComparator implements Comparator<Map.Entry<String, Integer>> {
@Override
public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
if(e1.getValue() == e2.getValue()) {
return e1.getKey().compareTo(e2.getKey());
}
return e1.getValue() > e2.getValue() ? -1 : 1;
}
}
public static void main(String[] args) {
String s = "ABCDABCDD";
Solution solution = new Solution();
System.out.println(solution.frequency(s));
}
}
Longest Substring With K Typed Characters
Given a string, return the longest contiguous substring that contains exactly k type of characters.
Return null if there does not exist such substring.
Assumptions:
The given string is not null and guaranteed to have at least k different characters.
k > 0.
Examples:
input = "aabcc", k = 3, output = "aabcc".
input = "aabcccc", k = 2, output = "bcccc".
public class Solution {
// Function to find the longest substring of a given string containing
// `k` distinct characters using a sliding window
public String longest(String input, int k) {
if (input == null || input.length() < k) {
return "";
}
Set<Character> window = new HashSet<>();
// stores the longest substring boundaries
int begin = 0, end = 0;
// Count array `freq` stores the frequency of characters present in the
// current window. We can also use a map instead of a count array.
int[] freq = new int[128];
for (int fast = 0, slow = 0; fast < input.length(); fast++) {
window.add(input.charAt(fast));
freq[input.charAt(fast)]++;
// if the window size is more than `k`, remove characters from the left
while(window.size() > k) {
// If the leftmost character's frequency becomes 0 after
// removing it in the window, remove it from the set as well
if (--freq[input.charAt(slow)] == 0) {
window.remove(input.charAt(slow));
}
slow++;
}
if (fast - slow > end - begin) {
end = fast;
begin = slow;
}
}
// return the longest substring found at `str[begin…end]`
return input.substring(begin, end + 1);
}
}
注意
if (--freq[input.charAt(slow)] == 0) {
window.remove(input.charAt(slow));
if (freq[input.charAt(slow)]-- == 0) {
window.remove(input.charAt(slow));
基础不好，如果是第二个情况，–其实是先判断完再行动，导致吐出 a b c 后才会 remove，而第一个先 – 了再判断
Shortest Substring With K Typed Characters
Given a string, return the shortest contiguous substring that contains exactly k type of characters.
Return an empty string if there does not exist such substring.
Assumptions:
The given string is not null.
k >= 0.
Examples:
input = "aabcc", k = 3, output = "abc".
input = "aabbbcccc", k = 3, output = "abbbc".
input = "aabcc", k = 4, output = "".
if (input.length() < k ) {
return "";
}
Map<Character, Integer> wordDict = new HashMap<>();
int slow = 0, minLen = Integer.MAX_VALUE, matchCount = 0, index = 0;
for (int fast = 0; fast < input.length(); fast++) {
char ch = input.charAt(fast);
Integer count = wordDict.getOrDefault(ch, 0) + 1;
wordDict.put(ch, count);
while (k == wordDict.size()) {
// 找到了
if (fast - slow + 1 < minLen) {
minLen = fast - slow + 1;
index = slow;
}
char leftmost = input.charAt(slow++);
Integer leftmostCount = wordDict.get(leftmost);
if (leftmostCount != null) {
wordDict.put(leftmost, leftmostCount - 1);
if (wordDict.get(leftmost) == 0) {
wordDict.remove(leftmost);
}
}
}
}
return minLen == Integer.MAX_VALUE ? "" : input.substring(index, index + minLen);
}
}
Longest Substring with At Most K Distinct Characters
Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2,
T is "ece" which its length is 3.
Longest Substring with At Most Two Distinct Characters
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”, T is "ece", return 3
public int lengthOfLongestSubstringTwoDistinct(String input) {
Map<Character, Integer> map = new HashMap<>();
int len = Integer.MIN_VALUE;
for (int fast = 0, slow = 0; fast < input.length(); fast++) {
char ch = input.charAt(fast);
map.put(ch, map.getOrDefault(ch,0) + 1);
while(map.size() > 2) {
char leftCh = input.charAt(slow);
map.put(leftCh, map.get(leftCh) - 1);
if (map.get(leftCh) == 0) {
map.remove(leftCh);
}
slow++;
}
len = Math.max(len, fast - slow + 1);
}
return len;
}
Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
public int minSubArrayLen(int num, int[] nums) {
int min = Integer.MAX_VALUE;
int sum = 0;
for (int slow = 0, fast = 0; fast < nums.length; fast++) {
sum += nums[fast];
while (sum >= num) {
min = Math.min(min, fast - slow + 1);
sum -= nums[slow++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/MPnaiL
感谢：她们都有题库在 github 上直接有，都是大神
