[C++] Sliding Window with the smallest window size
Intuition\n Describe your first thoughts on how to solve this problem. \nSliding Window with the smallest window size\n\n# Approach\n Describe your approach to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSliding Window with the smallest window size\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- move the window from left to right\n  - if `1` is too much, drop the left-most `1`\n  - drop the `0` on the left side\n- compare the current window (substring) with our best substring so far\n  - if the new substring is shorter, update our best substring\n  - if the length are the same, compare them to find the lexicographically smaller one\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    // time/space: O(n)/O(1)\n    string shortestBeautifulSubstring(string s, int k) {\n        int n = s.size(), count1 = 0, pos = 0, len = INT_MAX;        \n        for (int l = 0, r = 0; r < n; r++) {\n            // count the number of `1`\n            if (s[r] == \'1\') count1++;\n            // if `1` is too much, drop the left-most `1`\n            while ((count1 > k) && (l < r)) if (s[l++] == \'1\') count1--;\n            // drop the `0` on the left side\n            while ((l < r) && (s[l] == \'0\')) l++;\n            // we need more `1`\n            if (count1 != k) continue;\n            // the current window is not the shortest\n            int new_len = r - l + 1;\n            if (new_len > len) continue;\n            // we find a shorter substring\n            if (new_len < len) {\n                pos = l, len = new_len;\n                continue;\n            }\n            // the new length is the same, find the lexicographically smaller substring\n            if (compare(s, l, pos, len)) pos = l;\n        }\n        \n        if (len == INT_MAX) return "";\n        return s.substr(pos, len);\n    }\nprivate:\n    // return true if `a` is lexicographically smaller than `b`\n    bool compare(const string& s, int a, int b, int len) {\n        for (int offset = 0; offset < len; offset++) {\n            if (s[a + offset] == s[b + offset]) continue;\n            return (s[a + offset] < s[b + offset]);\n        }\n        return true;\n    }\n};\n```
['Sliding Window', 'C++']