리트코드 - 76. Minimum Window Substring

리트코드 - 76. Minimum Window Substring

출처 - https://leetcode.com/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 두 문자열 s와 t의 길이가 각각 m과 n일 때, s의 최소 윈도우 부분 문자열을 반환하세요. 이때, 이 윈도우는 t의 모든 문자(중복 포함)를 포함해야 합니다. 만약 그러한 부분 문자열이 없다면, 빈 문자열 ""을 반환하세요.

테스트 케이스는 답이 유일하도록 생성됩니다.

풀이코드

class Solution {
    public String minWindow(String s, String t) {
        int sl = s.length();
        int tl = t.length();

        if (sl < tl) {
            return "";
        }

        Map<Character, Integer> mh = new HashMap<>();

        for (char c : t.toCharArray()) {
            mh.put(c, mh.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> h = new HashMap<>();
        int l = 0;
        int r = 0;
        int minLen = Integer.MAX_VALUE;
        int index = 0;
        int match = 0;
        int mhSize = mh.size();

        while (r < sl) {
            char c = s.charAt(r);
            h.put(c, h.getOrDefault(c, 0) + 1);

            if (mh.containsKey(c) && h.get(c).equals(mh.get(c))) {
                match++;
            }

            while (match == mhSize) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    index = l;
                }

                char lc = s.charAt(l);
                h.put(lc, h.get(lc) - 1);

                if (mh.containsKey(lc) && h.get(lc) < mh.get(lc)) {
                    match--;
                }

                l++;
            }

            r++;
        }

        if (minLen == Integer.MAX_VALUE) { 
            return "";
        }

        return s.substring(index, index + minLen);
    }
}

생각

요구사항을 정리해보면 다음과 같다.

• s의 부분문자열에서 t에서 사용된 모든 알파벳을 사용할 것
• 가장 크기가 작은 값을 찾을 것

가장 적합한 로직은 슬라이딩 윈도우(투포인터)라고 생각했다.

Map에다가 t의 문자열이 몇 개 나왔는지 담아서 s를 슬라이드 윈도우를 통해 이동하면서 앞에서 만든 Map과 갯수비교를 하면 된다. 만들어진 값은 최솟값이라는 보장이 없으므로, 이 때 left를 이동하면서 작은 값을 찾아 갱신하면 된다.

코드설명

1. 필요한 데이터 구조

mh (mustHave): 문자열 t에서 각 문자의 빈도를 저장하는 해시맵(Map)
h (have): 현재 슬라이딩 윈도우 내 문자의 빈도를 저장하는 해시맵(Map)
l(left), r(right): 윈도우의 좌우 경계를 나타내는 두 개의 포인터
match: mh와 h에서 일치하는 문자의 개수
minLen: 최소 길이의 부분 문자열을 찾기 위한 최소 길이 변수
startIdx: 최소 길이를 찾았을 때의 시작 인덱스

 

2. 알고리즘 과정

(1) t의 문자 빈도를 mh에 저장
t를 순회하며 mh 맵에 각 문자의 개수를 저장

(2) r 포인터를 이동하면서 h에 문자를 추가
r 포인터를 이동하면서 현재 문자들을 h 맵에 저장
이때 h의 값이 mh의 값과 동일해지는 경우 match를 +1 증가. Integer 비교는 객체 비교이므로 equals()를 사용해야한다.

(3) match 값이 mh 크기와 동일한 경우
만약 match == mh.size()가 되면, 현재 윈도우가 t의 모든 문자를 포함했다는 의미이므로 최소 길이(minLen)를 갱신한다.

(4) l 포인터를 이동하여 최소 길이를 최적화
l을 이동시키면서 더 짧은 유효한 부분 문자열이 있는지 확인하고, 윈도우에서 제거된 문자가 mh에 있는 값이라면 match 값을 감소시켜야 함.

(5) 최적의 minLen 갱신 후 정답 반환
최소 길이를 저장한 minLen을 이용하여 s의 최소 부분 문자열을 반환.

 

3. 예제

s = "DADDABEC", t = "ABC"

단계	l	r	윈도우	match	minLen
초기	0	0	""	0	MAX_VALUE
1	0	5	"DADDA"	2	MAX_VALUE
2	0	6	"DADDAB"	3	7("DADDAB")
3	1	6	"ADDAB"	3	6("ADDAB")
4	2	6	"DDAB"	3	5("DDAB")
5	3	6	"DAB"	3	4("DAB")
6	3	7	"ABEC"	3	4("ABEC")