76. Minimum Window Substring - Streak 14

t를 전부 포함하는 최소 길이의 부분 문자열을 찾는 문제였다.

일단 최소 상태를 유지해야 하니 투 포인터가 떠올랐는데, "어떻게" 최소 상태를 유지할것인지에 대한 문제는 조금 까다로웠다.

나의 경우, 문자열이 포함되었을 때부터 왼쪽 끝을 당겨오면서 t를 포함하는지 체크하였다.

이때, 한 문자의 길이는 1이므로 왼쪽 문자의 이탈은 오른쪽에 바로 채워지지 않는 이상 더 짧아지기 어렵고, 따라서 항상 최소 상태 유지가 가능했다.

class Solution {
    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        int[] cnt = new int[58];
        int[] need = new int[58];
        for(int i = 0; i<t.length(); i++) need[t.charAt(i)-'A']++;
        int min = Integer.MAX_VALUE;
        String ret = "";
        while(right < s.length()){
            int now = s.charAt(right) - 'A';
            cnt[now]++;
            right++;
            while(check(cnt, need) && left <= right){
                if(min > right - left + 1){
                    ret = s.substring(left, right);
                    min = right - left + 1;
                }
                int before = s.charAt(left) - 'A';
                cnt[before]--;
                left++;
            }
        }
        return ret;
    }
    private boolean check(int[] cnt, int[] need){
        for(int i = 0; i<cnt.length; i++)
            if(cnt[i] < need[i]) return false;
        return true;
    }
}

/**
최소 상태 유지가 관건
 */

현재는 58까지 순회해서 check를 검사하므로, 해시맵과 같은 자료구조를 사용한다면 상수배가 줄어 좀 더 빠를 것이다.

 

 

---

 

 

라고 마칠려고 했는데, O(n+m) 풀이를 요구받았다.

사실 현재 풀이는 이미 O(n+m)인데, 이 말은 마치 이것보다 더 느린 풀이가 있다는 말처럼 들렸다.

그래서 곰곰히 생각해봤고, O(mlogn)의 다소 재밌는 풀이를 생각해봤다.

1. 최소 길이 부분 문자열은 반드시 그보다 긴 문자열에 포함된다.
2. 문자열의 길이와 포함/미포함 여부는 최소 길이 문자열을 기준으로 T/F 구조가 된다.
3. 따라서, 매개변수 탐색이 적용 가능하다.

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;

        int lo = t.length(), hi = s.length();
        int bestL = -1, bestLen = Integer.MAX_VALUE;

        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            int start = existsWindowOfLen(s, need, mid);
            if (start != -1) {
                if (mid < bestLen) { bestLen = mid; bestL = start; }
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return bestL == -1 ? "" : s.substring(bestL, bestL + bestLen);
    }

    private int existsWindowOfLen(String s, int[] need0, int L) {
        if (L <= 0) return -1;
        int[] need = new int[128];
        int missingKinds = 0;
        for (int c = 0; c < 128; c++) {
            need[c] = need0[c];
            if (need[c] > 0) missingKinds++;
        }

        int[] win = new int[128];
        int satisfied = 0;

        if (L <= s.length()) {
            for (int i = 0; i < L; i++) {
                int c = s.charAt(i);
                if (need[c] > 0 && ++win[c] == need[c]) satisfied++;
            }
            if (satisfied == missingKinds) return 0;
        } else return -1;

        for (int r = L; r < s.length(); r++) {
            int add = s.charAt(r);
            int rem = s.charAt(r - L);
            if (need[add] > 0 && ++win[add] == need[add]) satisfied++;
            if (need[rem] > 0 && win[rem]-- == need[rem]) satisfied--;
            if (satisfied == missingKinds) return r - L + 1;
        }
        return -1;
    }
}