Leetcode — 76. Minimum Window Substring (中文)

問題連結: https://leetcode.com/problems/minimum-window-substring/

問題會給兩個字串s, t
求回傳在s中最小長度的子字串(稱為window), window需包含在t出現的所有字元(字元出現順序不用一樣,但數量需要一樣)
若無法找到符合條件的window, 則回傳空字串即可

一些已知條件:

• 1 <= s.length, t.length <= 105
• s and t consist of English letters.
• 期許可用O(n)來解決這題 (面試如果遇到這類題, 感覺就算寫得出來 也會被這樣要求)

例子: 
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC" 
ADOBEC, BECODEBA, CODEBA, BANC 等子字串都符合,故回傳達條件最短子字串

想法:

我對這種題目很不在行, 但面試很喜歡問這類的問題 所以硬著頭皮也想要搞懂
我一開始實在不知從何下手, 大概猜的到要用兩個pointer來幫助我們用O(n)來解決問題

如果毫無技巧 想要硬要解的話就是用暴力解法
假設i是我們的起始點, j是我們的終點, 我們一直把j往右移直到我們找到符合條件的子字串
最後只寫得出下面的code:

public String minWindow(String s, String t) {
        if(t.length()>s.length())
            return "";
        int[] map = new int[256];
        for(char c:t.toCharArray())
            map[c]++;
        
        String rst = "";
        int slen = s.length(), tlen = t.length();
        for(int i=0;i<slen;i++)//start
        {
            if(map[s.charAt(i)]==0)
                continue;
            for(int j=i+tlen;j<=slen;j++) //end
            {
                String temp = s.substring(i,j);
                if(checkValid(map, temp, t))
                {
                    if(rst.length()==0 || (j-i)<rst.length())
                        rst = temp;
                    break; // since we have found the min len of the substring starting at i
                }
            }
        }
        return rst;
    }
    public boolean checkValid(int[] map, String s, String t){
        int[] tempMap = new int[256];
        for(char c:s.toCharArray())
            tempMap[c]++;
        for(int k=0;k<256;k++)
        {
            if(map[k]>tempMap[k])
                return false;
        }
        return true;
    }

⚠️時間複雜度為O(n²), 若在Leetcode上跑, 雖然大部分的case都成功, 但最後會在倒數第二個case 以TLE 而失敗收場

我們要如何改進我們的時間複雜度?

先前的程式碼, 我們是固定起點pointer i, 然後慢慢移動pointer j, 看各substring的組合個別是不是有符合題目條件;
找到後, 再把起點的pointer i 往右移, 又開始慢慢移動pointer j, 做重複的動作
這些動作中, 我們其實不停地重複檢查到部分字串
因此 如果我們可以在第一次檢查後, 利用已確定合格的window
再把你確定合格的window往左關 往右開 的這種方式 來找另一個也可以達條件的window, 直到window不能再移動了

下圖我就直接來用我們最一開始的例子來利用圖做解說 —

👉 目標是在 "ADOBECODBANC" 中找到 長度最小 且又包含 "ABC" 的window
程式邏輯:

我們先固定左邊i, 然後j就也從起點開始 一直往右擴張window, 直到找到合乎條件的window 就停下來
因為j確定是包含所有一定需要的, 我們這時候改縮小window左邊的空間,
把一開始固定的i往右縮減window, 直到window已不合乎條件, 我們又停下來 不把窗戶關小了 (因為也沒意義,現狀的已經不合乎條件, 再關小也沒有助於讓窗戶合乎條件)
再重複上述的動作, j又繼續擴張 ,直到窗戶合乎條件, i又繼續縮減直到窗戶不合乎條件,...

step 1: (i跟j都在起點)

step 2: j 在找到符合條件的地方 停下 (此時組成一個valid window "ADOBEC")

step 3: i 往右開始關窗戶 但現階段讓我們的窗戶又不valid了 所以代表我們又要往右開窗戶了

step 4: 這次j 往右開到最底才讓現有的window合乎條件 那我們來看能不能把左邊的窗戶關小一點

step 5: 窗戶往右關小一格時, 現有window仍然合乎條件, 我們也可以放心繼續把窗戶關小

step x: 一直關都發現我們一直可以得到新的合乎條件的window

關到這時, 發現現在的window已不合乎條件, 因此想要把窗戶開大的時候,卻發現j無法再往右 因此程式結束

所以我們在這個開關窗戶的途中, 也必須把我們得到最小的窗戶記錄起來, 也因此可以得到最終答案是"BANC" 而非最一開始找到的第一個窗戶

以下為3ms 的程式碼, 贏過96%的人:

public String minWindow(String s, String t) {
        if(s.length()<t.length())
            return "";
        int[] map = new int[256];
        for(char c: t.toCharArray())
            map[c]++;
        //the number of chars we need to find 
        int num = t.length(); 
        int[] validWindow = new int[]{-1,-1};
        int minLen = s.length()+1;
        int i = 0, j = 0;
        while(j<s.length())
        {
            if(map[s.charAt(j)]>0)
                num--; //found 1 qualified number 
            map[s.charAt(j)] --; 
            //num == 0 means now the window is valid 
            //try to see if we can move i to shrink the window
            while(num==0) 
            {
                if((j-i+1) < minLen)
                {
                    validWindow[0] = i;
                    validWindow[1] = j;
                    minLen = j-i+1;
                }
                map[s.charAt(i)]++;
                if(map[s.charAt(i)]>0)
                    num++;
                i++;
            }
            j++;
        }
        return validWindow[0]==-1?"":
                s.substring(validWindow[0], validWindow[1]+1);
    }

時間複雜度為O(n), 空間複雜度則是常數O(1)