[LeetCode] 76. Minimum Window Substring 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Minimum Window Substring

---

문제 요약 (Minimum Window Substring)

문자열 s와 t가 주어진다.
s 안에서 t의 모든 문자를 개수까지 포함하는
가장 짧은 연속 부분 문자열(substring) 을 반환하라.

• 순서 상관 ❌
• 부분 문자열 (연속) ⭕
• 중복 문자 개수까지 고려 ⭕

문제 링크
https://leetcode.com/problems/minimum-window-substring/

---

 

🤔 처음 떠올린 아이디어

문제 내에서 시간 복잡도 O(m+n) 으로 해결하려면...

연속된 구간 중에서
조건을 만족하는 가장 짧은 구간을
한 번의 순회로 찾을 수는 없을까?

---

 

💡 핵심 깨달음: 슬라이딩 윈도우

문제를 다시 보면 구조가 명확해진다.

• 연속된 구간
• 조건 만족 여부 존재
• 최소 길이

👉 Two Pointer / Sliding Window

• Right 포인터 → 조건을 만든다
• Left 포인터 → 조건을 깨뜨릴 때까지 줄인다

---

 

🧠 이 문제의 핵심 난관: 조건 판별

조건은 단순히
“t의 문자가 들어있는가?” 가 아니다.

❗ 개수까지 포함해야 한다

그래서 먼저 해야 할 일은: t의 문자 빈도 계산

t = "AABC"
need = { A:2, B:1, C:1 }

---

 

⚠️ 잘못된 접근: 매번 전체 비교

처음엔 이런 생각이 들 수 있다.

현재 윈도우의 빈도와
t의 빈도를 매번 비교하면 되지 않을까?

하지만 이 방식은

• 매번 Map 전체 비교
• 코드 복잡해짐
• 성능도 좋지 않다

👉 여기서 사고를 한 단계 바꿔야 한다.

---

⭐ 핵심 아이디어: formed

중요한 질문은 이것이다.

지금 윈도우에서 필요한 문자들이 모두 충족되었는가?

그래서 다음 개념을 도입한다.

• required → t에 등장하는 서로 다른 문자 개수
• formed → 현재 윈도우에서 필요 개수를 만족한 문자 종류 수

---

🔁 전체 흐름 정리

1. right를 이동하며 문자 빈도 증가
2. 어떤 문자가 필요 개수를 처음 만족하면 formed++
3. formed == required가 되는 순간 → 현재 구간은 답 후보
4. 이 상태에서 left를 이동하며 → 가능한 한 최소로 줄인다.
5. 조건이 깨지면 다시 right 이동

 

📌 핵심 포인트

• Right → 조건을 만든다
• Left → 조건을 깨뜨릴 때까지 줄인다
• 조건 판단은 오직 formed == required
  
  

---

💻 코드 (Java) (HashMap + formed 방식)

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {

        if (s.length() < t.length()) return "";

        // 1️⃣ t의 문자 빈도
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int required = need.size();
        Map<Character, Integer> window = new HashMap<>();

        int formed = 0;
        int left = 0, right = 0;

        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;

        // 2️⃣ Sliding Window
        while (right < s.length()) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);

            if (need.containsKey(c)
                && window.get(c).intValue() == need.get(c).intValue()) {
                formed++;
            }

            // 3️⃣ 조건 만족 시 left 줄이기
            while (left <= right && formed == required) {

                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }

                char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);

                if (need.containsKey(leftChar)
                    && window.get(leftChar) < need.get(leftChar)) {
                    formed--;
                }

                left++;
            }

            right++;
        }

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

 

💻 코드 (Java) (빈도 배열 + count 방식)

• tFreq[c] > 0
  → 아직 이 문자가 더 필요하다
• tFreq[c] == 0
  → 필요한 개수만큼 정확히 채웠다
• tFreq[c] < 0
  → 필요한 개수보다 더 많이 들어왔다

class Solution {

  public String minWindow(String s, String t) {
    int[] tFreq = new int[128];
    for (char c : t.toCharArray()) {
      tFreq[c]++;
    }

    int left = 0;
    int right = 0;
    int minLen = Integer.MAX_VALUE;
    int minLeft = 0;
    int count = 0;
    int tLen = t.length();

    while (right < s.length()) {
     // tFreq[문자]-- > 0 이면 → 이 문자는 아직 t에서 필요했던 문자라는 뜻
      if (tFreq[s.charAt(right++)]-- > 0) {
        count++; // s의 문자가 t에 있기 때문에 count를 증가시킨다.
      }

      if (count == tLen) {
        // left를 이동시키며 불필요한 문자 제거
        // tFreq < 0 이면 t에 필요 없는 문자이거나 초과된 문자
        while (left < right && tFreq[s.charAt(left)] < 0) { 
          tFreq[s.charAt(left++)]++;
        }

        if (right - left < minLen) {
          minLen = right - left;
          minLeft = left;
        }
        
        
        // left를 한 칸 이동시켜 조건을 일부러 깨뜨림
        // 다음 최소 window를 찾기 위한 준비
        tFreq[s.charAt(left++)]++; 
        count--; // 필요한 문자 하나가 빠졌으므로 count 감소
      }

    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);

  }
}

📈 시간 / 공간 복잡도

• 시간 복잡도 → 각 포인터가 한 번씩만 이동: O(N)
• 공간 복잡도 → 문자 빈도 Map 사용: O(1) (알파벳 기준)

---

📝 이번 문제에서 얻은 깨달음

• substring + 최소 길이 → 슬라이딩 윈도우
• 단순 포함 여부가 아니라 문자 개수까지 관리해야 하는 문제는 👉 HashMap + 카운트 조합
• 조건은 “전체 비교”가 아니라 상태로 관리
• 조건을 만족했다고 멈추지 말고 👉“지금이 최소인가?”를 계속 확인해야 진짜 정답
• 투 포인터 문제는 확장 → 조건 만족 → 축소 흐름을 머릿속에 그리는 게 중요