java_minimum_window_substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Examples

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= $10^5$
• s and t consist of uppercase and lowercase English letters.

Follow up:

Could you find an algorithm that runs in O(m + n) time?

解析

給定兩個字串 s, t

要求寫一個演算法找出 s 的子字串中包含 t 字串所有字元的最短子字串

s 的子字串 p 代表 p 中所有字元都在 s 出現過且每個字元必須跟 s 的相鄰狀態相同

所以題目要找子字串 p 必須要

1. 包含所有 t 的字元

2. 必須是字元相連性跟原本 s 相同

3. 必須是最短的

第一個條件可以透過 hashmap 的方式把 t 的所有字元出現次數紀錄下來比對

第二個相鄰狀態可以透過 slide-window 方式來保證

第3個條件 可以知道最理想的狀態是 剛好子字串長度跟 t 字串長度一樣

              所以從子字串長度 == t 字串長度 且累計配對字元數相等時

              就可以不斷更新 最小子字串長度直到把所有 s 的可能右界都走完 就可以找到最小的那個長度了

具體作法是大致分成三大步驟

1 在 slide-window 還沒有包含足夠多的字元時， 把右界往右

2 當符合條件具有足夠多的字元時，更新當 slide-window 比上一次符合條件小時，更新 slide-window 的 size 並且紀錄當下左右界

3 開始把左界左移，並且檢查當下 slide-window 是否有更小

具體作法如下圖

程式碼

public class Solution {
  public String minWindow(String s, String t) {
    int sLen = s.length(), tLen = t.length();
    String result = "";
    if (sLen < tLen || sLen == 0 || tLen == 0) {
      return result;
    }
    int[] sFreq = new int[256], tFreq = new int[256];
    int count = 0;
    int minW = sLen + 1, left = 0, right = -1, subLeft = -1, subRight = -1;
    for (int pos = 0; pos < tLen; pos++) {
      tFreq[t.charAt(pos)]++;
    }
    while(left < sLen) {
      // check if slide window is enough large
      if (right + 1 < sLen && count < tLen) {
        if (sFreq[s.charAt(right+1)] < tFreq[s.charAt(right+1)]) {
          count++;
        }
        sFreq[s.charAt(right+1)]++;
        right++;
      } else {
        if (right - left + 1 < minW && count == tLen) {
          minW = right - left + 1;
          subLeft = left;
          subRight = right;
        }
        if (sFreq[s.charAt(left)] == tFreq[s.charAt(left)]) {
          count--;
        }
        sFreq[s.charAt(left)]--;
        left++;
      }
    }
    if (subLeft != -1) {
      result = s.substring(subLeft, subRight+1);
    }
    return result;
  }
}

困難點

1. 需要理解透過 HashTable 確認字元出現個數的方法
2. 需要知道 slide-window 找尋可能子字串的方式

Solve Point

• 初始化 s_freq , t_freq 兩個 HashTable 用來各自紀錄 s, t 的字元次數出現狀況, count= 0 用來紀錄 s match 到 t 的字元個數， left = 0, right = -1, sub_left = -1, sub_right = -1, minW = len(s)+1
• 先把 t 的字元次數紀錄在 t_freq
• 當 left < len(s) 做以下運算
• 當 right + 1 < len(s) && count < len(t) 時 , 代表 還沒蒐集夠子字串字元 做以下運算
• 更新 s_freq[s[right+1]] += 1
• 當 s_freq[s[right+1]] ≤ t_freq[s[right+1]] 時 代表 該字元需要被納入 , 更新 count = count+1
• 更新 right = right + 1
• 當 right + 1 == len(s) || count == len(t) 時，做以下運算
• 當 right - left + 1 < minW 且 count == len(t) 時 代表已經蒐集足夠字元當子字串， 更新 minW = right - left + 1 , 更新 sub_left = left, sub_right = right
• 當 s_freq[s[left]] == t_freq[s[left]] 時 , 代表要左移的字元有被算入 count 之中 , 更新 count = count - 1 來做還原
• 更新 s_freq[s[left]] -= 1, left = left + 1
• 當跑到最後 sub_left ≠ -1 代表有找到子字串所以回傳 s[sub_left: sub_right+1], 否則回傳 “”