최소 창 부분문자

풀이

해쉬맵을 통해 문자별로 갯수를 새면서 문자가 0이 되는 순간의 문자를 확인하고 최소인지 확인하면 된다. 어렵

과정

1. t의 각 문자별로 해쉬맵에 저장한다
2. 문자를 순서대로 순회하며 부분문자열의 끝에 입력한다
3. 조회하는 문자가 해쉬맵 키에 있을 경우 숫자를 올린다
4. 부분문자열이 비어있지 않고, 부분문자열의 맨 앞 키가 요구하는 갯수를 초과하게 부분문자열에 들어있거나 요구하는 문자가 아닐 경우 제거한다.
5. 5.의 조건에 해당하지 않는 문자가 맨앞이 될때까지 반복
6. 부분문자열이 t의 문자들을 1개씩 소유할 경우 해당 문자가 여태 확인한 문자열중 최소인지 확인하고 최소일 경우 최소문자열로 선택

순서도

코드

import java.util.*;
class Solution {

    private int m;
    private int n;
    private Map<Character, Integer> map;

    public String minWindow(final String s, final String t) {
        m = s.length();
        n = s.length();
        map = new HashMap<>();
        for(final char c : t.toCharArray()){
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        String answer = "";
        int min = Integer.MAX_VALUE;
        String subString = "";
        for(final char c : s.toCharArray()){
            subString += c;
            if (map.containsKey(c)) {
                map.replace(c, map.get(c) - 1);
            }
            while(!subString.isEmpty() && (map.getOrDefault(subString.charAt(0),0) < 0 || !map.containsKey(subString.charAt(0)))){
                if (map.containsKey(subString.charAt(0))){
                    map.replace(subString.charAt(0), map.get(subString.charAt(0)) + 1);
                }
                subString = subString.substring(1);
            }
            if (isSubString()){
                if (subString.length() < min){
                    answer = subString;
                    min = subString.length();
                }
            }
        }
        return answer;
    }

    private boolean isSubString(){
        for(final int cnt : map.values()){
            if (cnt > 0){
                return false;
            }
        }
        return true;
    }
}