Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/description/

Minimum Window Substring - LeetCode

 

두 문자열이 주어질 때 두번째 문자열이 첫번째 문자열에 모두 포함될 수 있는 최소 길이를 찾는 문제이다.

 

부분 문자열을 찾기 위해 좌우측 끝을 슬라이딩 하며 찾아주었다. 이 때 문자열이 포함되는지 여부는 Map 자료구조를 이용해 주었다. 중복되는 문자도 있을 수 있으므로 Map의 Key를 문자로 하고 반복 값을 Value로 해주었다.

 

우측을 증가 시키며 문자열을 확인해 주었으며, 문자열이 확인된 이후에는 좌측을 증가 시켜 문자의 최소 길이를 측정해주었다. 완성된 코드는 아래와 같다.

  
import java.util.*;  
  
public class Solution {  
    public String minWindow(String s, String t) {  
  
        // t의 문자열 정보 저장  
        Map<Character, Integer> chkMap = new HashMap<>();  
        for(char c : t.toCharArray()){  
            chkMap.put(c, chkMap.getOrDefault(c, 0) + 1);  
        }  
  
        // 슬라이딩 되는 문자열 저장  
        Map<Character, Integer> curMap = new HashMap<>();  
  
        // t의 문자열의 총 개수  
        int complete = t.length();  
        // t의 문자열과 현재 슬라이딩 중인 문자열의 개수가 같은 정도  
        int maked = 0;  
        String answer = "";  
  
        // 좌측  
        int l = 0;  
        // 우측을 증가시키며 체크  
        for(int r = 0; r < s.length(); r++){  
            char right = s.charAt(r);  
            // 현재 우측 문자의 포함여부 확인  
            if(chkMap.containsKey(right)){  
                int value = chkMap.get(right);  
                int curValue = curMap.getOrDefault(right, 0) + 1;  
                curMap.put(right, curValue);  
                // 동일 문자가 나오는 경우 필요한 문자인지 체크  
                if(curValue <= value) maked++;  
            }  
  
            // 좌측 문자의 최대값 찾기  
            while(complete == maked){  
                String now = s.substring(l, r + 1);  
                answer = answer.length() == 0 || now.length() < answer.length() ? now : answer;  
  
                char left = s.charAt(l);  
                if(chkMap.containsKey(left)){  
                    int value = chkMap.get(left);  
                    int curValue = curMap.get(left) - 1;  
                    curMap.put(left, curValue);  
                    if(curValue < value) maked--;  
                }  
  
                // 우측이 고정된 상태에서 좌측을 증가시키며 체크  
                l++;  
            }  
        }  
  
        return answer;  
    }  
}