본문 바로가기

Algorithm/코드 풀이

LeetCode: 76번 (Minimum Window Substring) [JAVA]

문제 링크

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

 

Minimum Window Substring - LeetCode

Can you solve this real interview question? Minimum Window Substring - Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If t

leetcode.com

풀이

전체적인 풀이 과정은 다음과 같다.

  1. 주어진 문자열 t의 길이가 s보다 크다면 애초에 답 성립이 불가능하므로 "" 반환
  2. 주어진 문자열 s와 t의 알파벳 정보를 담을 배열을 각각 생성 (길이 52)
  3. s와 t를 t의 길이만큼만 알파벳 정보 카운트
  4. 이후 투 포인터를 활용해, start와 end에 각각 0과 t.length()-1을 초기화 후 while문을 통해 반복
    1) 만약 현재까지의 부분 문자열 알파벳 정보가, 충분히 t를 커버할 수 있다면 길이 비교를 통해 더 작은 부분 문자열을 저장. 이후 start를 하나 앞으로 이동시키며 빠진 알파벳 정보를 배열에서 제거
    2) 만약 충분히 t를 커버할 수 없다면, 끝 부분인 end를 하나 뒤로 이동시키며 해당 알파벳 정보를 배열에 추가
  5. 탐색 이후 답에 맞는 부분 문자열이 없다면, "" 반환
  6. 있다면 해당 부분 문자열을 반환

 t를 커버할 수 있는 s의 부분 문자열을, 단순히 이중 for문을 통해 계속 잘라 비교를 하게 되는 경우 시간 복잡도가 커진다. 이에 이전의 잘라낸 부분 문자열 정보를 바탕으로, 추가된 알파벳의 정보를 추가하거나 제거를 하여 시간 복잡도를 줄여야 한다.
 우선 문자열 t를 커버하는 s의 부분 문자열이 존재하려면, 최소 s의 길이가 t와 같거나 커야하기 때문에, 그렇지 않다면 빈 문자열을 반환한다. 그 다음에는 s와 t의 부분 문자열과 문자열 속 알파벳 정보를 담을 배열을 생성한다. 이 때 배열의 길이는 52로, 소문자와 대문자 알파벳을 모두 커버하기 위함이다. 그 다음에는 우선적으로 t의 길이만큼만, s와 t에 속한 알파벳들의 정보를 카운트한다.
 그 다음에는 투 포인터를 바탕으로 while 탐색을 진행한다. 우선 start에 0, end에 현재까지 탐색한 길이인 t.length()-1을 넣고, 다음에 따라 로직을 진행한다. 만약 현재 s의 부분 문자열이 t를 커버할 수 있다면, 해당 부분 문자열 길이가 가장 작은지 비교를 진행하고 가장 작은 부분 문자열 길이를 저장한다. 이후에는 다음 탐색을 위해, start를 다음으로 옮기면서 빠지게 된 알파벳의 정보를 배열에서 제거한다. 반대로 현재 s의 부분 문자열이 t를 커버할 수 없다면, 추가로 알파벳 정보를 넣어줘야 하기 때문에 end를 하나 뒤로 이동시키고, 추가된 알파벳 정보를 배열에 추가해준다.
 앞선 반복을 통해 탐색을 완료한 후, 만약 맞는 부분 문자열이 없다면 빈 문자열을 반환해주고 있다면 해당 부분 문자열을 반환해주면 된다.

 

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }

        int[] alphabetsInfoOfT = new int[52], alphabetsInfoOfS = new int[52];

        for (int i = 0; i < t.length(); i++) {//문자열 t 길이만큼만 알파벳 카운트
            count(t.charAt(i), alphabetsInfoOfT);
            count(s.charAt(i), alphabetsInfoOfS);
        }

        int start = 0, end = t.length() - 1;
        int bestStart = -1, bestEnd = s.length() + 1;

        while (end < s.length()) {
            if (isIncluded(alphabetsInfoOfT, alphabetsInfoOfS)) {//현재의 부분 문자열이 t를 커버한다면
                if (end - start < bestEnd - bestStart) {//좀 더 작은 길이라면
                    bestStart = start;
                    bestEnd = end;
                }
                remove(s.charAt(start), alphabetsInfoOfS);//첫 번째 문자 삭제
                ++start;
            } else {//끝 부분 문자 추가
                ++end;
                if (end < s.length()) {
                    count(s.charAt(end), alphabetsInfoOfS);
                }
            }
        }

        if (bestStart == -1) {//맞는 부분 문자열이 없다면
            return "";
        }

        return s.substring(bestStart, bestEnd + 1);
    }

    void count(char c, int[] alphabetsInfo) {//해당 알파벳 정보를 배열에 추가
        if ('a' <= c && c <= 'z') {
            ++alphabetsInfo[c - 'a'];
        } else {
            ++alphabetsInfo[c - 'A' + 26];
        }
    }

    void remove(char c, int[] alphabetsInfo) {//해당 알파벳 정보를 배열에서 삭제
        if ('a' <= c && c <= 'z') {
            --alphabetsInfo[c - 'a'];
        } else {
            --alphabetsInfo[c - 'A' + 26];
        }
    }

    boolean isIncluded(int[] alphabetsInfoOfT, int[] alphabetsInfoOfS) {//현재까지의 부분문자열이 t를 커버하는지
        for (int i = 0; i < 52; i++) {
            if (alphabetsInfoOfT[i] > alphabetsInfoOfS[i]) {
                return false;
            }
        }

        return true;
    }
}

결과