Sliding Window Detail Explanation.
Intuition\nThe code finds beautiful substrings with exactly k ones in the given string.\n\n# Approach\nIt uses two pointers to traverse the string, keeping trac
# Intuition\nThe code finds beautiful substrings with exactly k ones in the given string.\n\n# Approach\nIt uses two pointers to traverse the string, keeping track of onesCount and the shortest beautiful substring found.\n\nIn this algorithm, we utilize two pointers, \'l\' and \'r,\' to scan the input string \'s\' while keeping track of \'onesCount,\' which counts the number of ones (\'1\'s) in the current substring. We also maintain \'shortestLength\' to record the length of the shortest beautiful substring discovered so far and \'startIndex\' to store its starting index. As we advance the \'r\' pointer through the string, we increment \'onesCount\' each time a \'1\' is encountered.\n\nWhen \'onesCount\' reaches the desired \'k\' value, indicating the presence of a beautiful substring, we initiate a while loop. If the length of the current beautiful substring (\'r - l + 1\') is shorter or equally short compared to the \'shortestLength\' seen before, we update \'shortestLength\' and create a fresh set of substrings by clearing \'ans.\' We add the current beautiful substring to \'ans\' and continue by moving the \'l\' pointer to contract the substring. If the \'l\' character is a \'1,\' we decrement \'onesCount.\'\n\nThis process is repeated as the \'r\' pointer is advanced, beautiful substrings are identified, and \'ans\' and \'shortestLength\' are updated. After completing the traversal of the input string, we ensure \'ans\' is sorted in lexicographical order to guarantee the returned substring is the smallest. Finally, we iterate through \'ans\' to select the beautiful substring with the same length as \'shortestLength\' and return it as the result. If no valid beautiful substring is found, we return an empty string.\n\n# Complexity\n- Time complexity:-\n\nApologies for the previous response. The time complexity of your code is O(n * (n + m * log(m))), where \'n\' is the length of the input string \'s,\' \'m\' represents the number of beautiful substrings in \'s,\' and the sorting step introduces a logarithmic factor.\n\n\n\n- Space complexity:\n\nThe space complexity of your code is O(m), where \'m\' is the number of beautiful substrings found in the input string \'s.\' This space is mainly due to the \'ans\' vector used to store these substrings, with other constant-space variables. The time complexity is O(n * (n + m * log(m))), where \'n\' is the length of the input string \'s,\' \'m\' is the number of beautiful substrings, and the sorting step introduces a logarithmic factor.\n\n# Code\n```\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string s, int k) {\n        int l = 0, r = 0;\n        int onesCount = 0;\n        int shortestLength = INT_MAX;\n        int startIndex = -1;\n        vector<string> ans;\n\n        while (r < s.length()) {\n            if (s[r] == \'1\') {\n                onesCount++;\n            }\n\n            while (onesCount == k) {\n                if (r - l + 1 <= shortestLength) {\n                    if (r - l + 1 < shortestLength) {\n                        ans.clear();  // Start a new set of substrings if shorter\n                    }\n                    shortestLength = r - l + 1;\n                    startIndex = l;\n                    ans.push_back(s.substr(startIndex, shortestLength));\n                }\n\n                if (s[l] == \'1\') {\n                    onesCount--;\n                }\n\n                l++;\n            }\n\n            r++;\n        }\n\n        if (startIndex == -1) {\n            return "";\n        }\n\n        sort(ans.begin(), ans.end());\n\n        for (int i = 0; i < ans.size(); i++) {\n            if (ans[i].length() == shortestLength) {\n                return ans[i];\n            }\n        }\n\n        return "";\n    }\n};\n\n```
['Sliding Window', 'C++']