# 76 Minimum Window Substring

給兩個String, S和T, 回傳S包含T的所有字母的最短substring。

T可能有重複的字母。

• Idea:

  1. brute force O(N^2). When find a s.charAt(i) in t, go through chars after it and collect all char in t. when got all chars, save current length. update min length

  2. O(MN) map(char, index) record the index of each char
     min length will be (the largest index - the smallest index).
     every time update map, update min length -> can't deal with duplicate letters

  3. O(N)
     use 2 map to save all characters' count in t and their counts in s
     use left, right pointer, indicating the most left position and most right position of substring in s.
     keep moving left, right pointer to make sure always have all char of t in between
     and keep track of the counts of each char
     * use a int count, to keep total number of chars of t, when count == t.length(), we got valid substring

• 紀錄一下不能處理duplicate的版本

  public class Solution {
      public String minWindow(String s, String t) {        
          /*
          a map to save all char of t and their idx
          an arry to save current idx of each char
          for each char in s
              if c in t, put idx in array, update min, max
  
          return substring(min,max+1);
          */
          if(s.equals(""))    return "";
  
          int max = -1, min = t.length();
          String minStr = "";
          Map<Character, Integer> map = new HashMap<>();
          int[] curIdx = new int[t.length()];//record each char of t's index in s
  
          for(int i=0; i<t.length(); i++){
              map.put(t.charAt(i), i);
              curIdx[i] = -1;
          }
  
          for(int i=0; i<s.length(); i++){
              char c = s.charAt(i);
              if(map.containsKey(c)){
                  int idx = map.get(c);
                  int visited = 0;
                  curIdx[idx] = i;
  
                  max = curIdx[0];
                  min = curIdx[0];
                  for(int j=0; j<curIdx.length; j++){                    
                      if(curIdx[j]!=-1){
                          max = Math.max(max, curIdx[j]);
                          min = Math.min(min, curIdx[j]);
                          visited++;
                      }
                      //System.out.println(min +"," + max);
                  }
                  if(visited == t.length()){
                      String curStr = s.substring(min, max+1);
                      //System.out.println(curStr);
                      if(minStr.equals("")) minStr = curStr;
                      else if(minStr.length() > curStr.length()) minStr = curStr;
                  }
              }
  
          }
  
          /*for(int i=0; i<curIdx.length; i++){
              System.out.println(t.charAt(i) + "," + curIdx[i]);
          }*/
  
          return minStr;
      }
  }
  

• Pseudocode:

  Map<Character, Integer> curr_count
  Map<Character, Integer> t_count
  int left = 0, right = 0;
  String res = "";
  
  count all chars in t and save in t_count
  
  while left and right can't move anymore
      move right pointer until contains all chars
      save current string
      move left pointer
  
  return res;
  

• Code: 把我卡住很久的是，移動left時我又再增加count，但這樣不對，因為right跑過那個位置時就已經加過了。後來搬到迴圈外面才跑出正確結果。

  public class Solution {
      public String minWindow(String s, String t) {
          int[] curr_count = new int[256];//current count of each number
          int[] t_count = new int[256];//count each number in t
          int count = 0;//keep total number of chars
          int left = 0, right = 0;
          String res = "";
  
          //count all chars in t and save in t_count
          for(int i=0; i<t.length(); i++){
              int c = (int)t.charAt(i);
              t_count[c]++;
          }
  
          //check if left is point to a char which t has **outside loop**
          int l = (int)s.charAt(left);
          curr_count[l]++;
          if(t_count[l]!=0 && curr_count[l] <= t_count[l]) count++;
  
          //while left and right can't move anymore
          for(; left < s.length(); left++){
              //after left moves, update count and curr_count
              if(left > 0){
                  int prev = (int)s.charAt(left-1);
                  curr_count[prev]--;
                  if(t_count[prev]!=0 && curr_count[prev] < t_count[prev]) count--;
              }
  
              //move right pointer until contains all chars
              while(count < t.length() && right < s.length()-1){
                  right++;
                  int r = (int)s.charAt(right);
                  curr_count[r]++;
                  if(t_count[r]!= 0 && curr_count[r] <= t_count[r]) count++;
              }
  
              //update shortest window
              if(count == t.length() && (res.equals("") || (right-left+1) < res.length()))
                  res = s.substring(left, right+1);
          }
  
          return res;
      }
  }