<Hard> Minimum Window Substring (LeetCode : C#)

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

📕 문제 설명

두 문자열 s, t와 각 길이가 주어질 때 t에 있는 모든 문자가 s에 포함되는 최소 길이의 substring 반환하기
(포함 안하면 "" 반환)

• Input
  두 문자열 s, t와 각 길이
• Output
  t에 있는 모든 문자 포함하는 최소 길이의 s의 substring

예제

시도 1. 각 index별로 가능한 substring 체크하기 (Brute Force)

실패 (시간 초과) O(N^3) -> 각 index별로 (n) 뒤 index 보기 (n) list에 포함되는지 확인 (n)..?

public class Solution {
    public string MinWindow(string s, string t) {

        string answer = "";
        List<char> chars = new List<char>(t);
        string currS = "";

        for (int i = 0; i < s.Length; i++)
        {
            int currIndex = i;
            chars = new List<char>(t);
            currS = "";
            while (currIndex < s.Length)
            {
                char currentC = s[currIndex];
                currS += currentC;
                if (chars.Contains(currentC))
                {
                    chars.Remove(currentC);
                    if (chars.Count == 0)
                    {
                        if (answer == "") answer = currS;
                        else answer = answer.Length < currS.Length ? answer : currS;
                        break;
                    }
                }
                currIndex++;
            }
            // 현재 index에서 모두 포함할때까지 돌기

        }

        return answer;
        
    }
}

풀이

투 포인터 방식으로 풀었다.

기본적인 아이디어는 다음과 같다.
1. 오른쪽 포인터를 t에 있는 모든 문자를 포함할 때까지 움직인다.
2. 왼쪽 포인터를 t에 있는 모든 문자를 포함하는 동안 움직이며 최소 길이를 갱신한다.
3. t를 모두 포함 안하게 되면 다시 1과 2를 반복한다. (이때 1)은 s의 마지막 문자를 볼 때까지 진행)
4. 모든 과정을 마친 후 저장된 최소 인덱스를 기반으로 s를 substring 하여 반환한다.

public class Solution {
    public string MinWindow(string s, string t) {
        int[] map = new int[128];
        foreach(char c in t) map[c]++;

        int count = t.Length, left = 0, right = 0, d = int.MaxValue, head = 0;

        while(right < s.Length) 
        {
            if(map[s[right]] > 0) // t 포함하는 문자면 count 세기
            {
                count--;
            }

            map[s[right]]--; // 문자 포함 표시
            right++;

             // count가 0되면 (즉, t 모두 포함하게 되면) -> left 한칸씩 옮기면서 최소 길이 갱신
            while(count == 0) 
            {
                // 왼쪽 옮긴 후 현재보다 더 짧으면 갱신 
                if(right - left < d)
                {
                    head = left;
                    d = right - head;
                } 
                
                if(map[s[left]] == 0) count++;

                map[s[left]]++; // 문자 제외 표시
                left++;
            }  
        }
        return d == int.MaxValue ? "" : s.Substring(head, d);
    }

}

결과