Leet code (Hard): 76. Minimum Window Substring (슬라이딩 윈도우) - JAVA

 

슬라이딩 윈도우를 깊이 공부할 수 있었던 문제다.

 

최대 길이를 구했던 여태까지의 문제와 다르게 최소 길이를 구하는 문제였다.

변수 설정, 반복문 설정 부터 모두 중요했던 문제다. 

 

• 시간 복잡도: O(n+m)
• 공간 복잡도: O(m)
• n: s의 길이
• m: t의 길

class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer> word = new HashMap<>();    // t의 문자를 문자, 갯수 매핑
        Map<Character,Integer> window = new HashMap<>();  // 윈도우의 문자, 갯수 매핑
        int minLength = Integer.MAX_VALUE;  // 윈도우 최소 길이
        int minLeft = 0;    // 윈도우 최소 길이의 left
        int minRight = 0;   // 윈도우 최소 길이의 right

        // word 세팅
        for(char c : t.toCharArray()){
            word.put(c, word.getOrDefault(c, 0) + 1);
        }

        int required = word.size();    // 목표 단어 갯수 (중복 제거)
        int formed = 0;  // 윈도우 내 목표 단어 갯수

        int left = 0, right = 0;

        while(right < s.length()){
            // 오른쪽 문자를 현재 문자로 세팅
            char curr = s.charAt(right);

            // 현재 문자를 윈도우에 추가
            window.put(curr, window.getOrDefault(curr, 0)+1);

            // 현재 문자가 word에 있고, 그 값이 필요량을 다 채웠다면 formed++
            if(word.containsKey(curr) && word.get(curr).intValue() == window.get(curr).intValue()){
                formed++;
            }

            // 모든 필요한 문자를 다 포함하는 경우, 
            // 1. 윈도우 축소하며 minLength 갱신
            // 2. 갱신 후 현재 left 문자를 윈도우에서 제외시키며 조건을 만족 여부(formed) 업데이트
            // 3. left 포인터를 다음으로 밀기
    		// -> 2번으로 인해 formed가 업데이트 되어 while 조건을 만족 안하게 되면 빠져나감. 
            while(left <= right && formed == required){
                char l = s.charAt(left);

                // 1. minLength 최소 윈도우 길이를 갱신
                if(right - left + 1 < minLength){
                    minLength = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }

                // 2. left 문자를 제거하며 윈도우 크기 축소
                window.put(l, window.getOrDefault(l, 0) - 1);
                if(word.containsKey(l) && word.get(l).intValue() > window.get(l).intValue()){
                    // 제거된게 유효한 문자였다면 formed--
                    formed--;
                }
				
                // 3. left 가리키는 포인터 뒤로 이동
                left++;
            }

            right++;
        }

        return minLength == Integer.MAX_VALUE ? "" : s.substring(minLeft, minRight + 1);
    }
}