[LeetCode][JAVA] 76. Minimum Window Substring

💡 문제

76. Minimum Window Substring

 (https://leetcode.com/problems/minimum-window-substring/submissions/1763182670/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 슬라이딩 윈도우(Sliding Window): 포인터 L(left), R(right)을 사용해 윈도우를 확장/축소하며 조건을 만족하는 최소 길이를 탐색.
• 빈도 카운팅(Frequency Counting):
  • need[c] = t에 필요한 각 문자의 총 개수
  • win[c] = 현재 윈도우에 포함된 각 문자의 개수
• 만족도 트래킹(formed/required):
  • required = 필요 문자 종류 수(need[c] > 0인 문자 개수)
  • formed = 현재 윈도우에서 정확히 필요 개수만큼 충족한 문자 종류 수
  • formed == required가 되면 모든 요구 조건을 충족 → 왼쪽을 최대한 줄여 최소 길이 갱신

---

🤓 문제 풀이

문자열 s에서 문자열 t의 모든 문자(중복 포함)를 포함하는 최소 길이 부분 문자열을 찾는다.
윈도우를 오른쪽(R)으로 확장하여 모든 요구(formed==required)가 충족되는 순간, 왼쪽(L)을 당겨 가능한 한 짧은 구간을 만든다. 이 과정을 문자열 끝까지 반복하면 전역 최소 길이를 구할 수 있다.

 

🔨 문제 설명

• 입력: 문자열 s, 문자열 t
• 출력: t의 모든 문자를 포함하는 s의 최소 창 부분 문자열. 없으면 "".

예)

• s = "ADOBECODEBANC", t = "ABC" → "BANC"
• s = "a", t = "a" → "a"
• s = "a", t = "aa" → ""

제약

• 1 <= m, n <= 1e5
• 영문 대/소문자로 구성(ASCII 128 배열로 처리 가능)

---

🔨 접근 방법

 

1. t를 순회하며 need[c]를 채우고, need[c] > 0인 서로 다른 문자 수를 required로 계산.
2. R을 0→n-1로 증가:
   • win[s[R]]++
   • 어떤 문자 rc가 필요했고(need[rc] > 0) 정확히 맞춰졌다면(win[rc] == need[rc]) formed++
3. formed == required일 때, 왼쪽을 줄이며 최소 길이 갱신:
   • 갱신 조건: R - L + 1가 더 작으면 bestLen/bestL 업데이트
   • win[s[L]]-- 후 필요치 미달이 되면 formed--, L 증가 종료
4. 전체를 순회 후, bestLen == INF면 "", 아니면 s.substring(bestL, bestL+bestLen) 반환

 

 

---

🔨 문제 풀이 과정

• 윈도우 확장(오른쪽 포인터 R 전진)으로 모든 요구를 충족하는 최초 지점을 찾는다.
• 충족된 순간부터 왼쪽 포인터 L을 최대한 당겨도 조건이 유지되는지 확인한다.
• 이 축소 과정에서 최소 길이를 갱신한다.
• 조건이 깨지는 순간 다시 확장(다음 R)으로 전환한다.

핵심 불변식: “축소 루프 진입 시점에는 formed == required를 반드시 만족한다.”

 

---

🔨 구현코드

package leetcode;

/**
 * 76. Minimum Window Substring
 * 슬라이딩 윈도우 + 문자열 해싱
 * https://leetcode.com/problems/minimum-window-substring/description/
 *
 * 길이가 각각 m과 n인 두 문자열 s와 t가 주어졌을 때,
 * t의 모든 문자(중복 포함)가 창에 포함되도록 s의 최소 창 부분 문자열을 반환합니다.
 * 이러한 부분 문자열이 없는 경우 빈 문자열 ""을 반환
 *
 * t의 각 문자가 몇 번 필요한지 need[c]에 기록.
 * 윈도우 [L..R] 안의 현재 개수를 win[c]로 관리.
 * need[c] > 0인 문자들 중, win[c] == need[c]가 된 종류의 개수를 formed로 셉니다.
 * formed == required(= 필요한 모든 문자 충족) 상태에서 최대한 왼쪽을 줄여 최소 길이를 갱신합니다.
 *
 * 예 1:
 * Input: s = "ADOBECODEBANC", t = "ABC"
 * 출력: "BANC"
 * 설명: 최소 창 하위 문자열 "BANC"에는 문자열 t의 'A', 'B', 'C'가 포함됩니다.
 *
 * 예제 2:
 * Input: s = "a", t = "a"
 * 출력: "a"
 * 설명: 전체 문자열 s는 최소 창입니다.
 *
 * 예제 3:
 * Input: s = "a", t = "aa"
 * 출력: ""
 * 설명: t의 'a'는 모두 창에 포함되어야 합니다.
 * s의 가장 큰 창에는 'a'만 있으므로 빈 문자열을 반환합니다.
 *
 * 제약 조건:
 * m == s.length
 * n == t. 길이
 * 1 <= m, n <= 105
 * s와 t는 대문자와 소문자로 구성되어 있습니다.
 *
 * 시간 복잡도 : O(m+n) - 각 문자는 최대 한 번 들오오고(확장), 한 번 나갑니다. (축소)
 * 공간 복잡도 : O(Σ) — 필요한 문자 종류 수(배열 128 또는 맵의 distinct 키 수).
 */
public class LeSolution02 {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // 문제 조건: 영문 대/소문자, 배열 128이면 충분
        int[] need = new int[128];
        int required = 0; // need[c] > 0인 서로 다른 문자 수

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (need[c] == 0) {
                required++;
            }
            need[c]++;
        }

        int[] win = new int[128];
        int formed = 0; //현재 윈도우에서 need를 만족한 문자 종류 수
        int L = 0;
        int bestL = 0;
        int bestLen = Integer.MAX_VALUE;

        for (int R = 0; R < s.length(); R++) {
            char rc = s.charAt(R);
            win[rc]++;

            // 이 문자가 필요한 종류였고, 이제 막 정확히 맞춰졌다면 formed++
            if (need[rc] > 0 && win[rc] == need[rc]) {
                formed++;
            }

            // 모든 요구를 만족했다면, 왼쪽을 당겨 최소 길이 시도
            while (formed == required) {
                if (R - L + 1 < bestLen) {
                    bestLen = R - L + 1;
                    bestL = L;
                }

                char lc = s.charAt(L++);
                win[lc]--;
                // 필요 문자였고 하나 빠져서 부족해지면 foremd--
                if (need[lc] > 0 && win[lc] < need[lc]) {
                    formed--;
                }
            }

        }

        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
    }

    public static void main(String[] args) {
        LeSolution02 sol = new LeSolution02();
        System.out.println(sol.minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(sol.minWindow("a", "a"));
        System.out.println(sol.minWindow("a", "aa"));
        System.out.println(sol.minWindow("aa", "aa"));
        System.out.println(sol.minWindow("ab", "b"));
    }
}

---

📚 풀이 보완

코드 설명 (핵심 라인)

• if (need[rc] > 0 && win[rc] == need[rc]) formed++;
  → 정확히 필요 개수에 도달했을 때만 증가해야 함(초과는 의미 없음).
• 축소 루프에서 win[lc] < need[lc]가 되는 순간 formed--
  → 더 이상 모든 요구를 만족하지 못하므로 축소 종료.
• “초과 충족”을 formed에 반영하는 실수
  → win[c] == need[c]일 때만 formed++
• 필요 없는 문자를 불필요하게 신경 쓰는 실수
  → need[c] == 0인 문자는 formed/required에 영향 없음.
• 빈 문자열/길이 비교 누락
  → s.length() < t.length()면 즉시 "" 반환.

---

📍 Plus+

 

• 유니코드/확장 문자셋:
  • 전 범위 문자가 올 수 있으면 Map<Character, Integer>로 변경
• 빠른 스킵 최적화(선택):
  • need[c]==0인 구간은 굳이 축소 루프 진입을 시도하지 않도록 분기
  • 실제 편익은 데이터 분포에 따라 상이(과최적화 주의)

간단한 테스트 팁

• 완전 매칭: s="aa", t="aa" → "aa"
• 불가능: s="a", t="aa" → ""
• 중복 필요: s="aab", t="aab" → "aab"
• 복합: s="abdaaacb", t="abc" → "acb"

 

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

시간 복잡도

• O(m+n)
  • 각 문자는 최대 한 번 윈도우에 들어오고(확장), 최대 한 번 나감(축소)

공간 복잡도

• O(Σ)
  • Σ는 문자셋 크기(여기선 ASCII 128). need/win 배열 크기 또는 Map의 distinct 키 수

요약

• 핵심 전략: 슬라이딩 윈도우에서 formed/required로 요구 충족 여부를 상수 시간에 판별
• 정답 갱신 타이밍: formed == required가 되는 매 순간, 왼쪽을 최대한 줄일 때
• 복잡도: 시간 O(m+n), 공간 O(Σ)

---

풀이 참고 로직

• 필요 문자 종류 수: required = count(need[c] > 0)
• 만족도 증가: if (need[rc] > 0 && win[rc] == need[rc]) formed++
• 만족도 감소: if (need[lc] > 0 && win[lc] < need[lc]) formed--
• 최소 길이 갱신: if (len < bestLen) best = [L, R]