C++ 9ms 14 lines


  • 1
    string minWindow(string s, string t) {
            string ans = s + 'a';                                   // make ans initial length larger than s for convenience
            int k = t.length(), freqs[256];                         
            memset(freqs, 0, sizeof(freqs));
            
            for (char c : t) { freqs[c]++; }                        // sample t to get all chars in t
            
            for (int l = 0, r = 0; r < s.length(); r++) {
                if (freqs[s[r]]-- > 0) { k--; }                     // only count if freqs is larger than zero
                if (k == 0) {
                    while (freqs[s[l]] < 0) { freqs[s[l++]]++; }    // move l to get shortest substr
                    
                    if (r - l + 1 < ans.length()) {
                        ans = s.substr(l, r - l + 1);               // record ans
                    }
                }
            }
            
            return ans.length() > s.length() ? "" : ans;                     
    }
    

  • 0
    J

    This is the most elegant piece of code I've seen in a while. Absolutely stunning.


Log in to reply
 

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