[LeetCode] 76. Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/description/?envType=daily-question&envId=2024-02-04

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Minimum Window Substring

문제 유형 : 투 포인터, 슬라이딩 윈도우

문제 난이도 : Hard

 

문제

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.

 

두 문자열 s와 t가 각각 m, n의 길이로 주어진다. s에 t의 모든 요소들이 포함된(중복까지 포함하여) 최소 길이의 부분 문자열을 구하여라.

없으면, 빈 문자열을 반환하라.

TC는 답이 단 하나 나오도록 되어있다.

 

풀이

만약 m의 길이가 n의 길이보다 짧은 경우, 불가능하므로 빈 문자열을 반환한다.

또한, m의 길이와 n의 길이가 같은 경우, 가진 요소가 하나다로 다르면 빈 문자열을 반환한다. 아니라면 s를 반환하면 된다.

그 외의 경우는 아래와 같다:

 

left와 right 포인터를 이용한다.

두 개의 해시맵을 만든다. 하나에는 t의 요소의 개수들을 저장시킨다.

하나에는 right를 올리면서 다른 하나의 해시맵에 요소의 개수를 추가시킨다.

만약 s의 해시맵이 t의 해시맵을 포합한다면, 유효한 부분 문자열이다.

그런 경우, 유효한 동안 left를 늘리고 해시맵에서 s[left]의 개수를 빼면서 길이를 줄여나가본다.

유요한 동안에 최소 길이를 비교하면서 업데이트하고,

모든 반복문이 끝나고 최소 길이와 그 인덱스에 따라서 부분 문자열을 반환한다.

업데이트된 적이 없으면, 빈 문자열을 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
    unordered_map<char, int> tmp;
    unordered_map<char, int> smp;
public:
	// s의 부분문자열이 t를 포함하는지 체크
    bool valid() {
        for(const auto &element : tmp) {
            if(element.second - smp[element.first] > 0) return false;
        }
        return true;
    }

    string minWindow(string s, string t) {
        const int n = t.size();
        const int m = s.size();
        pair<int, int> minPoint{0, 1e9};
        // 기저 사례 1: t가 더 긴경우, 불가능하므로 빈 문자열 반환
        if(n > m) return "";
        // 기저 사례 2: 길이가 같은 경우, 가진 요소가 완전히 같아야 함
        if(n == m) {
            for(int i = 0; i < n; i++) {
                tmp[t[i]]++;
                smp[s[i]]++;
            }
            if(valid()) return s;
            else return "";
        }
		
        // t의 요소의 개수 저장
        for(int i = 0; i < n; i++) {
            tmp[t[i]]++;
        }

		// 투 포인터, 슬라이딩 윈도우를 이용하여 최소길이 업데이트
        int left = 0;
        for(int right = 0; right < m; right++) {
            smp[s[right]]++;
            bool flag = false;
            // 유효한 동안, 최소 길이 없데이트 및 left증가함으로 길이 단축 시도
            while(flag || valid()) {
                if(right-left < minPoint.second - minPoint.first) {
                    minPoint = {left, right};
                }
                smp[s[left]]--;
                if(tmp[s[left]] - smp[s[left]] <= 0) flag = true;
                else flag = false;
                left++;
            }
            //cout << s.substr(minPoint.first, minPoint.second - minPoint.first + 1) << endl;
        }

		// 업데이트가 한 번도 없으면 빈 문자열 반환. 아니라면 부분문자열 반환
        if(minPoint.second == 1e9) return "";
        return s.substr(minPoint.first, minPoint.second - minPoint.first + 1);
    }
};