C# O(n) solution


  • 0
    H
    public string MinWindow(string s, string t) {
            Dictionary<char, int> counts = new Dictionary<char, int>();
            for(int i = 0; i < t.Length; i++) counts[t[i]] = counts.ContainsKey(t[i]) ? counts[t[i]] + 1 : 1;
            
            int j = 0, k = 0, nzc = counts.Count, min = int.MaxValue;
            string minstr = "";
            
            while(k < s.Length) {
                if (counts.ContainsKey(s[k])) {
                    counts[s[k]]--;
                    if (counts[s[k]] == 0) nzc--;
                    while (nzc == 0) {
                        int len = k - j + 1;
                        if (len < min) {
                            min = len;
                            minstr = s.Substring(j, len);
                        }
                        
                        if (counts.ContainsKey(s[j])) {
                            counts[s[j]]++;
                            if (counts[s[j]] == 1) {
                                nzc++;
                            }
                        }
                        
                        j++;
                    }
                }
                k++;
            }
            
            return minstr;
        }
    

Log in to reply
 

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