[LeetCode] 76. Minimum Window Substring - Java

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

Minimum Window Substring - LeetCode

---

문제

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 there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

 

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

 

Follow up: Could you find an algorithm that runs in O(m + n) time?

---

풀이

풀이 과정

알파벳 대,소문자로 이루어진 두 문자열 s와 t가 주어졌을 때 t에 있는 모든 문자를 포함하는 s의 부분문자열 중 가장 작은 부분문자열을 구하는 문제이다. 정답에 해당하는 부분문자열이 없는 경우에는 빈 문자열을 return한다.

우선 타겟이 되는 t문자열의 길이가 s문자열의 길이보다 큰 경우 정답이 존재할 수 없으므로 바로 빈 문자열을 return 한다.

// 타겟이 되는 t문자열의 길이가 s문자열의 길이보다 큰 경우 정답이 존재할 수 없음
// 바로 빈 문자열을 return
if(t.length() > s.length()) return "";

 

예시 1번을 기준으로 부분문자열을 탐색하는 전체적인 과정은 다음과 같다.

1. 타겟이 되는 문자열 t의 모든 문자와 그 개수를 Map에 저장

 

2. 포인터 두 개를 이용하여 범위를 이동하며 탐색

 

3. Map에 있는 모든 문자를 포함할 때 까지 오른쪽 인덱스를 증가

---

 

4. Map에 있는 모든 문자를 포함하는 경우, 다시 Map에 있는 문자가 필요해 질 때까지 왼쪽 인덱스를 증가

 

5. 만들어진 범위가 최소 부분문자열의 길이보다 작은 경우 최소 부분문자열 업데이트, 단 왼쪽 인덱스는 증가 이전까지의 범위

문자열을 모두 탐색할 때 까지 위의 과정을 반복한다.

 

각 단계를 코드로 구현하면 다음과 같다.

먼저 필요한 문자와 그 개수를 저장할 Map을 하나 선언하고 t의 각 문자를 순회하며 Map에 저장한다.

// 필요한 문자와 개수를 저장할 Map
Map<Character, Integer> target = new HashMap<>();
// 필요한 모든 문자와 개수를 Map에 저장
for(int i = 0; i < t.length(); i++) {
    Character c = t.charAt(i);
    target.put(c, target.getOrDefault(c, 0) + 1);
}

 

탐색에 필요한 변수를 선언

// 최소 부분 문자열
String minSub = s;
// 탐색중인 범위의 왼쪽 인덱스
int left = 0;
// 탐색중인 범위의 오른쪽 인덱스
int right = 0;
// 필요한 문자의 총 개수
int count = t.length();
// 타겟 문자를 모두 포함한 부분문자열이 존재하는지 여부
boolean find = false;

 

오른쪽 인덱스가 탐색할 문자열 s의 끝에 도달할 때 까지 탐색을 반복한다.
만약 오른쪽 인덱스에 해당하는 문자가 Map에 존재하는 경우, 즉 정답이 되기 위해서 포함되어야 하는 문자인 경우 Map에서 해당 문자의 개수를 감소시키고 개수가 0이상인 경우 필요한 문자의 총 개수도 감소시킨다.
t의 모든 문자를 포함한 부분문자열을 찾았으므로 존재 여부를 업데이트한다.

개수가 0 이상인 경우에만 필요한 문자의 총 개수를 감소시키는 이유는 만약 "A"라는 문자가 1개 포함 되어야할 때 탐색중인 범위에 "A"가 두 개가 존재한다면 Map에 존재하는 "A"의 개수는 -1이 될 것이지만 실제로 필요한 문자의 총 개수는 1개만 감소해야하기 때문이다.

// 문자열의 끝까지 탐색할 때 까지 반복
while(right < s.length()) {
    // 오른쪽 인덱스의 문자 탐색
    Character end = s.charAt(right);
    // 필요한 문자인 경우
    if(target.containsKey(end)) {
        // target에서 해당 문자의 카운트 감소
        target.put(end, target.get(end) - 1);
        // 필요한 문자의 총 개수 감소
        if(target.get(end) >= 0) count--;
    }

    // 필요한 문자의 총 개수가 남아있으면 필요한 모든 문자를 포함할 때 까지 오른쪽 인덱스를 증가시키며 재탐색
    right++;
    if(count > 0) continue;
    
    // 필요한 문자를 모두 포함한 경우
    // 정답이 될 수 있는 부분 문자열 존재 여부 업데이트
	find = true;
    
    ...
}

 

정답이 되기위해 필요한 문자를 모두 포함할 때 까지 오른쪽 인덱스가 이동했다면, 다시 필요한 문자가 생길 때 까지 왼쪽 인덱스를 증가시키며 탐색한다.
왼쪽 인덱스에 해당하는 문자가 Map에 존재하는 경우 이번에는 반대로 Map에서 해당 문자의 개수를 증가시키고 개수가 0보다 큰 경우 필요한 문자의 총 개수도 증가시킨다.

개수가 0보다 큰 경우에만 필요한 문자의 총 개수를 증가시키는 이유도 마찬가지이다.
정답이 되기 위해서 필요한 문자 "A"의 개수가 1개인데 현재 탐색범위에 포함된 "A"가 2개라면 그 중 하나가 포함되지 않더라도 정답이 되는데는 영향이 없기 때문이다.

// 필요한 문자의 개수가 다시 0보다 커질 때 까지 왼쪽 인덱스를 증가시키며 범위를 감소시킴
while(count == 0) {
    // 왼쪽 인덱스의 문자 탐색
    Character start = s.charAt(left);
    // 필요한 문자인 경우
    if(target.containsKey(start)) {
        // target에서 해당 문자의 카운트 증가
        target.put(start, target.get(start) + 1);
        // 필요한 문자의 총 개수 증가
        if(target.get(start) > 0) count++;
    }

    // 왼쪽 인덱스 증가
    left++;
}

 

위의 과정을 종료했을 때 탐색 범위가 최소 부분문자열의 길이보다 작은 경우 현재 범위에 해당하는 부분문자열을 최소 부분문자열로 업데이트 한다. 이 때 왼쪽 인덱스는 증가한채로 존재하기 때문에 이전 인덱스를 포함하여 체크한다.

// 현재 탐색 범위가 최소 부분문자열 길이보다 작은 경우
if(right - (left - 1) < minSub.length()) {
    // 현재 탐색범위의 문자열을 최소 부분문자열로 저장
    minSub = s.substring(left - 1, right);
}

 

모든 탐색이 종료되고 정답이 될 수 있는 부분 문자열을 찾은 경우에는 최소 부분 문자열을 return 하고, 찾지 못한 경우 에는 빈 문자열을 return 한다.

// 정답이 되는 부분 문자열을 찾은 경우 최소 부분문자열을 return
// 찾지 못한 경우 빈 문자열을 return
return find ? minSub : "";

---

최종 코드

class Solution {
    public String minWindow(String s, String t) {
        // 타겟이 되는 t문자열의 길이가 s문자열의 길이보다 큰 경우 정답이 존재할 수 없음
        // 바로 빈 문자열을 return
        if(t.length() > s.length()) return "";
        
        // 필요한 문자와 개수를 저장할 Map
        Map<Character, Integer> target = new HashMap<>();
        // 필요한 모든 문자와 개수를 Map에 저장
        for(int i = 0; i < t.length(); i++) {
            Character c = t.charAt(i);
            target.put(c, target.getOrDefault(c, 0) + 1);
        }
        
        // 최소 부분 문자열
        String minSub = s;
        // 탐색중인 범위의 왼쪽 인덱스
        int left = 0;
        // 탐색중인 범위의 오른쪽 인덱스
        int right = 0;
        // 필요한 문자의 총 개수
        int count = t.length();
        // 타겟 문자를 모두 포함한 부분문자열이 존재하는지 여부
        boolean find = false;
        
        // 문자열의 끝까지 탐색할 때 까지 반복
        while(right < s.length()) {
            // 오른쪽 인덱스의 문자 탐색
            Character end = s.charAt(right);
            // 필요한 문자인 경우
            if(target.containsKey(end)) {
                // target에서 해당 문자의 카운트 감소
                target.put(end, target.get(end) - 1);
                // 필요한 문자의 총 개수 감소
                if(target.get(end) >= 0) count--;
            }
            
            // 필요한 문자의 총 개수가 남아있으면 필요한 모든 문자를 포함할 때 까지 오른쪽 인덱스를 증가시키며 재탐색
            right++;
            if(count > 0) continue;
            
            // 필요한 문자를 모두 포함한 경우
            // 정답이 될 수 있는 부분 문자열 존재 여부 업데이트
            find = true;
            
            // 필요한 문자의 개수가 다시 0보다 커질 때 까지 왼쪽 인덱스를 증가시키며 범위를 감소시킴
            while(count == 0) {
                // 왼쪽 인덱스의 문자 탐색
                Character start = s.charAt(left);
                // 필요한 문자인 경우
                if(target.containsKey(start)) {
                    // target에서 해당 문자의 카운트 증가
                    target.put(start, target.get(start) + 1);
                    // 필요한 문자의 총 개수 증가
                    if(target.get(start) > 0) count++;
                }
                
                // 왼쪽 인덱스 증가
                left++;
            }
            
            // 현재 탐색 범위가 최소 부분문자열 길이보다 작은 경우
            if(right - (left - 1) < minSub.length()) {
                // 현재 탐색범위의 문자열을 최소 부분문자열로 저장
                minSub = s.substring(left - 1, right);
            }
            
        }
        
        // 정답이 되는 부분 문자열을 찾은 경우 최소 부분문자열을 return
        // 찾지 못한 경우 빈 문자열을 return
        return find ? minSub : "";
    }
}

---