76. Minimum Window Substring

• 두 문자열 s, t 가 주어졌을 때 t에 있는 모든 글자를 포함하는 s의 부분 문자열 중 가장 길이가 짧은 것을 구하는 문제.

• t에 있는 모든 글자를 포함하기만 하면 되고 순서는 지킬 필요가 없으므로 t 그리고 s의 부분 문자열에 대해서 속해있는 문자의 출현 빈도를 세어서 비교하면 된다.
• 먼저 s의 길이가 t보다 작으면 애초에 t에 속한 모든 문자를 포함할 수 없으므로 답이 없는 것 “” 으로 한다.
• t에 속한 문자의 출현 빈도를 세어 저장 tCnt해둔다.
• s의 최소 부분 문자열 범위 min을 [0, Integer.MAX_VALUE]로 (Integer.MAX_VALUE는 값이 없음을 표시하기 위해), 현재 부분 문자열 범위 cur를 [0, 0]으로 초기화한다.
• 부분 문자열 범위 cur을 다음과 같은 규칙으로 확장, 축소하면서 조건을 만족하는 범위를 찾는다.
• 부분 문자열의 출현 빈도 sCnt와 대상 문자열의 출현 빈도 tCnt 를 비교하여 현재 부분 문자열에 대상 문자열이 포함되는지 확인 contains한다.
• 포함되지 않는 경우 contains == false 부분 문자열의 범위를 뒷쪽으로 확장 ++cur[1] 하여 더 많은 문자가 부분 문자열에 포함되도록 한다.
• 범위가 확장되었으므로 새로 추가된 문자 s.charAt(cur[1])를 부분 문자열의 출현 빈도 배열 sCnt에 추가 ++sCnt[ordAt(s, cur[1])]한다.
• 포함되는 경우 contains == true 부분 문자열의 범위를 앞쪽에서 축소 --cur[0] 하여 더 적은 문자열로도 조건을 만족할 수 있는지 확인한다.
• 범위가 축소되었으므로 제거된 문자 s.charAt(cur[0])를 부분 문자열의 출현 빈도 배열 sCnt에서 제거 --sCnt[ordAt(s, cur[0])]한다.
• 문자열의 범위가 문자의 길이 M = s.length()를 초과하지 않는 범위에서 확장, 축소를 진행한다.

class Solution {
    final int L = 2 * ('z' - 'a' + 1);
    
    int ordAt(String s, int i) {
        if (i >= s.length()) {
            return 0;
        }
        int c = s.charAt(i);
        return c >= 'a' && c <= 'z'?
            c - 'a' : c - 'A' + L / 2;
    }
    
    public String minWindow(String s, String t) {
        int M = s.length();
        int N = t.length();
        if (M < N) return "";
        
        int[] sCnt = new int[L];
        int[] tCnt = new int[L];
        for (int i = 0; i < N; ++i) {
            ++tCnt[ordAt(t, i)];
        }
        
        int[] min = new int[]{ 0, Integer.MAX_VALUE };
        int[] cur = new int[]{ 0, 0 };
        while (cur[1] <= M) {
            int minLength = min[1] - min[0];
            int length = cur[1] - cur[0];
            boolean contains = true;
            for (int i = 0; i < L; ++i) {
                if (sCnt[i] < tCnt[i]) {
                    contains = false;
                    break;
                }
            }
            if (contains) {
                if (length < minLength) {
                    min[0] = cur[0];
                    min[1] = cur[1];
                }
                --sCnt[ordAt(s, cur[0])];
                ++cur[0];
            } else {
                ++sCnt[ordAt(s, cur[1])];
                ++cur[1];
            }
        }
        if (min[1] == Integer.MAX_VALUE) return "";
        return s.substring(min[0], min[1]);
    }
}