leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0076.cpp (732B)

      1 class Solution {
      2   public:
      3     string minWindow(string s, string t) {
      4         vector<int> remaining(128, 0);
      5         for (char c : t)
      6             remaining[c]++;
      7 
      8         int required = t.size();
      9         int min = INT_MAX, start = 0, left = 0, i = 0;
     10         while (i <= s.size() && start < s.size()) {
     11             if (required) {
     12                 if (i == s.size()) break;
     13                 if (--remaining[s[i++]] >= 0) required--;
     14             } else {
     15                 if (i - start < min) {
     16                     min = i - start;
     17                     left = start;
     18                 }
     19                 if (++remaining[s[start++]] > 0) required++;
     20             }
     21         }
     22         return min == INT_MAX ? "" : s.substr(left, min);
     23     }
     24 };