[Sliding Window][Hard] 76. Minimum Window Substring

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

 

Q. s와 t 두개의 문자열이 주어질 때, t의 모든 문자가 나타나는 s 의 sub string 중 최소 길이를 갖는 sub string을 찾아라. 

 

Solution. 

 모든 t가 s에 출현해야 하고, t에 중복된 문자가 존재 할 수 있으므로, hash를 써서 문자 freq buffer를 사용해야 할 듯 하다. 

 슬라이딩 윈도우 기본 로직에 맞게 모든 문자열을 찾으면 해당 sub string을 찾고 최소 길이인지 확인한다. 

 이후 left에 대해 다음 t에 나오는 char가 나오는 시점까지 left를 당긴다.

 그대로 위 로직을 반복한다. 

 

 로직대로 코드를 써 본다. 

 

 

public string MinWindow(string s, string t) 
{
    Dictionary<char, int> dictBuff = new Dictionary<char, int>();
    for(int k = 0; k < t.Length; ++k)
    {
        if(!dictBuff.ContainsKey(t[k]))
            dictBuff.Add(t[k], 1);
        else 
            ++dictBuff[t[k]];
    }

    int left = -1;
    int right = 0;
    int retLeft = 0, retLen = -1;
    for(; right < s.Length; ++right)
    {
        char cur = s[right];
        if(dictBuff.ContainsKey(cur))
        {
            if(left < 0)    left = right;
            --dictBuff[cur];
            bool foundAll = true;
            foreach(var key in dictBuff.Keys) 
            {
                if(dictBuff[key] > 0)
                {
                    foundAll = false;
                    break;
                }
            }

            if(foundAll) 
            {
                if(retLen==-1 || right-left+1<retLen)
                {
                    retLeft = left;
                    retLen = right-left+1;
                }

                // Poll left.
                ++dictBuff[ s[left] ];
                ++left;
                while(left<right && !dictBuff.ContainsKey(s[left]))
                    ++left;

                // redo this one.
                ++dictBuff[cur];
                --right;
            }
        }
    }
    return retLen>0 ? s.Substring(retLeft, retLen) : "";
}

 

조금 더 최적화의 여지는 있지만, 그래도 적절한 결과를 얻었다.

 

 

Note) 이전엔 왠지 풀 수 없었던 문제.

 다량의 문제를 풀어보기 시작하면서 문제를 보는 직관 능력도 크진 않지만 향상됨을 느낀다.