132ms Time O(N) C# 2-pointer + Dictionary Solution


  • 1
    L

    132ms is the fastest one in C# OJ so far.

    public string MinWindow(string s, string t) {
        int left = 0, right = 0, count = t.Length, minLen = int.MaxValue;
        int[] resultIndex = {0, 0};
        Dictionary<char, int> hist = new Dictionary<char, int>();
        for (int i = 0; i < t.Length; i++)
            if (!hist.ContainsKey(t[i])) hist.Add(t[i], 1);
            else hist[t[i]]++;
        while (left < s.Length && !hist.ContainsKey(s[left])) right = ++left;
        while (right < s.Length){
            if (hist.ContainsKey(s[right]) && --hist[s[right]] >= 0 && count-- == 1)
                while (count == 0){
                    if (resultIndex[1] == 0 || right - left + 1 < minLen)
                    { resultIndex[0] = left; resultIndex[1] = right - left + 1; }
                    minLen = right - left + 1;
                    if (minLen == t.Length) return s.Substring(resultIndex[0], resultIndex[1]);
                    if (++hist[s[left++]] > 0) count++;
                    while (left < s.Length && !hist.ContainsKey(s[left])) left++;
                }
            if (right++ - left + 1 >= minLen){
                if (++hist[s[left++]] > 0) count++;
                while (left < s.Length && !hist.ContainsKey(s[left])) left++;
            }
        }
        return s.Substring(resultIndex[0], resultIndex[1]);
    }
    

    Another solution by using array to map it. It costs 128ms.

    public string MinWindow(string s, string t) {
        int left = 0, right = 0, count = t.Length;
        int[] resultIndex = {0, int.MaxValue}, map = new int[128];
        for (int i = 0; i < 128; i++) map[i] = int.MinValue;
        for (int i = 0; i < t.Length; i++)
            if (map[t[i]] == int.MinValue) map[t[i]] = 1;
            else map[t[i]]++;
        while (left < s.Length && map[s[left]] == int.MinValue) right = ++left;
        while (right < s.Length){
            if (map[s[right]] != int.MinValue && --map[s[right]] >= 0 && count-- == 1)
                while (count == 0){
                    if (resultIndex[1] == 0 || right - left + 1 < resultIndex[1])
                    { resultIndex[0] = left; resultIndex[1] = right - left + 1; }
                    if (resultIndex[1] == t.Length) return s.Substring(resultIndex[0], resultIndex[1]);
                    if (++map[s[left++]] > 0) count++;
                    while (left < s.Length && map[s[left]] == int.MinValue) left++;
                }
            if (right++ - left + 1 >= resultIndex[1]){
                if (++map[s[left++]] > 0) count++;
                while (left < s.Length && map[s[left]] == int.MinValue) left++;
            }
        }
        return s.Substring(resultIndex[0], resultIndex[1] == int.MaxValue ? 0 : resultIndex[1]);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.