Beats 100 % submissions | Sliding Window | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nMy first thought was to find substrings that contain exactly k number of \'1\'s. Since 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy first thought was to find substrings that contain exactly k number of \'1\'s. Since we need to return the shortest such substring, the substrings should be compared first by length and then lexicographically.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Traverse the string using a sliding window approach.\n2. Keep a count of \'1\'s in the current window.\n3. When the count of \'1\'s equals k, trim leading \'0\'s and store the valid substring.\n4. Continue sliding the window by moving the left pointer and decrementing the count of \'1\'s accordingly.\n5. Collect all valid substrings and sort them using the custom comparator.\n6. Return the first element from the sorted list, which will be the shortest and lexicographically smallest substring.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n        O(nlogn)\n- Space complexity:\n        \n    The space complexity is O(m) where m is the total length of all valid substrings collected in the vector.      \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    struct comparator{\n        bool operator()(const string &s1,const string &s2) const{\n            if(s1.size() != s2.size())\n                return s1.size() < s2.size();\n            return s1<s2;\n        }\n    };\n\n    string shortestBeautifulSubstring(string s, int k) {\n        int n=s.size();\n        int i=0,j=0,ct=0;\n        vector<string>temp;\n       \n        while(j<n) {\n            if(s[j]==\'1\'){\n                ct++;\n            }\n            if(ct < k) {\n                j++;\n            }else if(ct==k) {\n                while(s[i]==\'0\') {\n                    i++;\n                }\n                string str=s.substr(i,j-i+1);\n                temp.push_back(str);\n\n                i++;\n                ct--;\n                while(s[i]==\'0\') {\n                    i++;\n                }\n                j++;\n            }\n        }\n\n        sort(temp.begin(),temp.end(),comparator());\n        \n        if(temp.empty()) return "";\n        return *(temp.begin());\n    }\n};\n```
['C++']