[leetcode 76] Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC"

Example 2:

Input: s = "a", t = "a" Output: "a"

 

Constraints:

• 1 <= s.length, t.length <= 105
• s and t consist of English letters.

문제 풀이:

- 두개의 포인터를 사용한 sliding window기법을 사용한다. t의 모든 문자열을 포함하는 end위치를 찾고 그 길이를 최소화하기 위해 start를 움직인다.

- 문자열 등장 횟수 저장을 위해 map을 사용한다.

 

1. t의 문자열을 hash map에 저장한다.

2. s의 문자열 전체를 돌며 t에 있는 문자가 등장하면 count를 감소시킨다. 

2-1. 그와 동시에 hash의 등장횟수도 감소시킨다. (hash의 모든 원소의 값이 0이라면 t의 문자열이 모두 등장했다는 의미이다. 3-2와 연결)

3. count가 0이 되면 모든 문자를 찾았다는 의미이므로 start를 움직이기 시작한다.

3-1. start가 업데이트 될때마다 최소 길이과 시작위치를 업데이트 해준다.

3-2. end가 지나가면서 hash[s[end]]--를 계속 해줬기 때문에 hash[s[start]]>0이라는 의미는 t문자열이 깨졌다는 걸 의미한다. 

4. 만약 minlen이 초기값이라면 t 문자열이 s에 존재하지 않는다는 의미이므로 빈 문자열을 리턴한다.

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.length();
        int m = t.length();
        
        if(n == 0 || m==0){
            return "";
        }
        
        if(n < m){
            return "";
        }
        
        string answer ="";
        unordered_map<char, int> hash;
        
        for(int i=0; i<m; i++){
            hash[t[i]]++;
        }
        int minLen = INT_MAX, minStart=0;
        int start=0, end=0, count = m;
        while(end<n){
            if(hash[s[end]]>0){
                count--;
            }
            hash[s[end]]--;
            end++;
            
            while(count == 0){
               
                if(end-start < minLen){
                    minLen = end-start;
                    minStart = start;
                }
                
                hash[s[start]]++;
                if(hash[s[start]] > 0){
                    count++;
                }
                start++;
            }
        }
        
        if(minLen != INT_MAX){
            answer = s.substr(minStart, minLen);
        }
        
        return answer;
        
    }
};