76.Minimum-Window-Substring

76. Minimum Window Substring

题目地址

https://leetcode.com/problems/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.

代码

Approach #1 Sliding Window

双指针 + 双字典 (需要匹配的字典，窗口内的字典)

1. 固定左边l, r++往右构建满足条件的map

2. 当满足条件，固定右边r，l++缩小右端检查是否满足map

Time Complexity && Space Complexity: O(|S| + |T|)

class Solution {
  public String minWindow(String s, String t) {
      if (s.length() == 0 || t.length() == 0) return "";

      // Dictionary which keeps a count of all the unique characters in t.
      Map<Character, Integer> dictT = new HashMap<Character, Integer>();
      for (int i = 0; i < t.length(); i++) {
          int count = dictT.getOrDefault(t.charAt(i), 0);
          dictT.put(t.charAt(i), count + 1);
      }
      // ans list of the form (window length, left, right)
      int[] ans = {-1, 0, 0};

      Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
      int required = dictT.size();
      int formed = 0;

      // Left and Right pointer
      int l = 0, r = 0;
      while (r < s.length()) {
          char c = s.charAt(r);
          int count = windowCounts.getOrDefault(c, 0);
          windowCounts.put(c, count + 1);

          if (dictT.containsKey(c) 
              && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
              formed++;
          }

          // Try and contract the window till the point where it ceases to be 'desirable'.
          while (l <= r && formed == required) {
              c = s.charAt(l);
              // Save the smallest window until now.
              if (ans[0] == -1 || r - l + 1 < ans[0]) {
                  ans[0] = r - l + 1;
                  ans[1] = l;
                  ans[2] = r;
              }
              // The character at the position pointed by the
              // `Left` pointer is no longer a part of the window.
              windowCounts.put(c, windowCounts.get(c) - 1);
              if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                  formed--;
              }
              // Move the left pointer ahead, this would help to look for a new window.
              l++;
          }

          // Keep expanding the window once we are done contracting.
          r++;   
      }

      return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
  }
}

Approach #2 Optimized Sliding Window

class Solution {
  public String minWindow(String s, String t) {
    if (s.length() == 0 || t.length() == 0) return "";

    Map<Character, Integer> dictT = new HashMap<Character, Integer>();
    for (int i = 0; i < t.length(); i++) {
      int count = dictT.getOrDefault(t.charAt(i), 0);
      dictT.put(t.charAt(i), count + 1);
    }
    int required = dictT.size();

    List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (dictT.containsKey(c)) {
        filteredS.add(new Pair<Integer, Character>(i, c));
      }
    }

    int l = 0, r = 0, formed = 0;
    Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
    int[] ans = {-1, 0, 0};

    while (r < filteredS.size()) {
      char c = filteredS.get(r).getValue();
      int count = windowCounts.getOrDefault(c, 0);
      windowCounts.put(c, count + 1);

      if (dictT.containsKey(c) &&
         windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
        formed++;
      }

      while (l <= r && formed == required) {
        c = filteredS.get(l).getValue();
        int end = filteredS.get(r).getKey();
        int start = filteredS.get(l).getKey();
        if (ans[0] == -1 || end - start + 1 < ans[0]) {
          ans[0] = end - start + 1;
          ans[1] = start;
          ans[2] = end;
        }

        windowCounts.put(c, windowCounts.get(c) - 1);
        if (dictT.containsKey(c) 
            && windowCounts.get(c).intValue() < dictT.gt(c).intValue()) {
          formed--;
        }
        i++;
      }
      r++;
    }

    return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
  }
}