Minimum Window Substring

문제를 찾던 와중에 투포인터/슬라이딩 윈도우 문제를 발견해서 풀어보았다. 슬라이딩 윈도우 유형의 문제는 굉장히 많지만 조금 특이하고 괜찮게 봤던 문제다.

t가 속하는 모든 s의 substring 중에 가장 짧은것을 뽑아내면 된다. 그리고 이 문제를 풀기 위해서 중요한 점은 다름아닌 맵을 사용하여 투포인터의 한 부분이 t의 전부를 만들었을때 계산을 해주어야한다.

left 포인터를 옮기는 조건은 최대로 줄일 수 있을만큼이다. 즉, t의 형태를 유지하면서 불필요한 알파뱃들을 빼주는 작업이 필요하다는 뜻이다. 그런데 중복되는 aa같은게 있기때문에 무턱대고 map1 == map2 하면은 틀리게 되어서 계속 비교해야 하나 생각했는데 내 실수였다.

t의 문자가 발견되면 그대로 cnt 를 하나씩 늘려서 만약 카운트가 t의 길이와 같게되면 left 를 옮겨주는 작업을 했으면 됐었다.

class Solution {
public:
    string minWindow(string s, string t) {
        map<char,int> hashMap; 
        map<char,int> trackMap; 
        int length = INT_MAX; 
        for(char& c : t) hashMap[c]++; 
        int left = 0, right = 0, letters = 0; 
        string answer = ""; 
        while(right < s.length()){ 
            if(hashMap.count(s[right])){
                trackMap[s[right]]++; 
                if(trackMap[s[right]] <= hashMap[s[right]]){
                    letters++; 
                }
            }
            if(letters >= t.length()){
                cout << "aa" << endl; 
                while(!hashMap.count(s[left]) || trackMap[s[left]] > hashMap[s[left]]){
                    trackMap[s[left]]--;
                    left++; 
                }
                if(right - left + 1 < length){
                    length = right - left + 1;  
                    answer = s.substr(left, length); 
                }
            }
            right++; 
        }
        return answer; 
    }
};