[LeetCode] 76. Minimum Window Substring

문제 링크

leetcode: 76. Minimum Window Substring

문제

• 문자열 s와 t가 주어진다.
• t에 존재하는 모든 문자를 포함하는 최소 길이의 substring을 s에서 찾아 반환한다.
• 존재하지 않는 경우 ""을 반환한다.

풀이

특정 구간의 좌, 우 인덱스를 l, r로 지정하고 해당 구간 내에 존재하는 문자들에 대한 정보를 확인하며 조건을 만족하는 구간을 업데이터 한다.

1. l과 r사이의 문자들이 t에 존재하는 모든 문자를 포함한다면 l위치를 증가시키면서 구간을 줄여나간다.
2. 현재 유지하고 있는 구간이 t에 존재하는 문자를 모두 포함하지 않는다면 r값을 증가시켜 구간을 늘려나간다.

구간 내에 모든 문자를 포함하는지는 unordered_map 자료구조에 t에 존재하는 문자별 개수를 카운트 한 후 해당 값을 s에서 등장하는 문자에 따라 감소시키고 증가시켜서 확인했다.

문자는 알파벳만 허용하기 때문에 한 번 확인하는데 최대 52번의 연산만 하면 되기 때문에 시간 초과가 일어날 걱정은 없다.

l과 r을 좌우 끝에 두고 범위를 줄여나가는 경우

이 경우는 최선의 케이스를 찾을 수 있다고 보장할 수 없다.
예를 들어

t = "ABC"
s = "ABCOOOOA"

위와 같은 상황에서 l, r에 위치한 문자 모두 t에 존재하는 문자일 경우 어떤 인덱스를 조정해야할지 명확하게 판단할 수 없기 때문이다. 만약 l값을 증가시킨 경우 결과는 BCOOOOA가 나오므로 오답이 된다.

코드

class Solution {
public:
    bool chk(unordered_map<char,int>& count_t){
        for(auto hash: count_t){
            if(hash.second>0) return false;
        }
        return true;
    }

    string minWindow(string s, string t) {
        int m, n;
        m = s.size(); n = t.size();
        if(m<n) return "";
        unordered_map<char,int> count_t;
        for(int i=0; i<n; i++) count_t[t[i]]++;

        int l,r, start, end;
        string answer;
        l=0; r=0;
        start = 0; end=INT_MAX;
        while(r<m){
            if(!count_t.contains(s[r])) {r++; continue;}
            count_t[s[r]]--;
            while(chk(count_t)){
                if(end-start>r-l) {
                    end = r+1; start = l;
                }
                if(count_t.contains(s[l])) count_t[s[l]]++; 
                l++;
            }
            r++;
        }

        if(end!=INT_MAX) return s.substr(start, end-start);
        else return "";
    }   
};

조건을 만족하는 경우마다 substr을 이용해 string타입의 변수를 업데이트 하는 방식으로 했다가 메모리 초과가 발생했었다.

인덱스 값만 변경하여 마지막에 substr을 활용했는데, 이렇게 최적화 할 수 있다면 그렇게 하는 게 맞는 것 같다.