滑动窗口解决字符串子串问题

对很多给定一个字符串，然后要求找到一个满足一定条件的子串的问题，一种比较通用的做法是借助一个MAP，或者是等价的int[128]数组，以及两个指针。由于可以将两个指针看作一个窗口，这种问题也可以叫做滑动窗口问题。下面是解决滑窗问题的一个模板。

public String slideWindow(String s, String t) {
  if(s.length() == 0 || t.length() == 0 || s.length() < t.length()) 
    return "";

  int[] map = new int[128]; //map
  int counter; //check whether the substring is valid
  int begin = 0, end = 0; //two pointers, the window
  int d; //the length of the substring

  for() { /* initialize the hash map here */}

  while(end < s.length()) {
    if(map[s[end++]]-- ?) { /* modify counter here*/}
    while(/* counter condition */) {
      /* update d here if finding minimum */
      //increase begin to make it invalid/valid again
      if(map[s[begin++]]++ ?) { /* modify counter here */ }
    }
    
    /* update d here if finding maximum */
  }
  return d /*? check initial condition*/ ? "" : s.substring(begin,begin + d);
}

76. Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

public String minWindow(String s, String t) {
        if(s.length() == 0 || t.length() == 0 || s.length() < t.length()) return "";
        
        int[] map = new int[128];
        int counter = t.length();
        int begin = 0, end = 0;
        int d = Integer.MAX_VALUE;
        int head = 0;
        
        for(Character c : t.toCharArray()) map[c] ++;
        
        while(end < s.length()) {
            if(map[s.charAt(end++)]-- > 0) counter --;
            
            while(counter == 0) {
                if(end-begin < d) d = end - (head = begin);
                if(map[s.charAt(begin++)]++ == 0)  counter ++;
            }
        }
        
        return d == Integer.MAX_VALUE ? "" : s.substring(head, head+d);
    }

438. Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList();
        if(s.length() == 0 || p.length() == 0 || s.length() < p.length()) return res;
        
        int[] map = new int[128];
        int begin = 0, end = 0, counter = p.length(), head = 0;
        
        for(char c : p.toCharArray()) map[c]++;
        while(end < s.length()){
            if(map[s.charAt(end++)]-- > 0) counter --;
            
            while(counter == 0 && begin<end) {
                if((end-(head=begin)) == p.length()) res.add(head);
                if(map[s.charAt(begin++)]++ == 0) counter++;
            }
        }
        return res;    
    }

3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", which the length is 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        
        int[] map = new int[128];
        int begin = 0, end = 0, d = Integer.MIN_VALUE, counter = 0;
        
        while(end < s.length()) {
            if(map[s.charAt(end++)]++ > 0) counter ++;
            
            while(counter > 0) {
                if(map[s.charAt(begin++)]-- > 1) counter --;
            }
        
            if(end - begin > d) {
                d = end - begin;
            }
        }
        return d;
    }