[Python3] Concise Solution with Detailed Explanation
Intuition\nThe problem requires finding a substring with exactly k occurrences of \'1\' that is the shortest in length and lexicographically smallest. A sliding
# Intuition\nThe problem requires finding a substring with exactly k occurrences of \'1\' that is the shortest in length and lexicographically smallest. A sliding window approach is ideal for maintaining a running count of \'1\'s in a substring, allowing us to efficiently check and update potential solutions as we iterate through the string.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use a sliding window with two pointers (`l` and `r`) to represent the current substring.\n2. Maintain a counter `count_ones` to track the number of \'1\'s in the current window.\n3. Expand the window by moving the right pointer `r` and updating `count_ones` whenever `s[r] == \'1\'`.\n4. When the count of \'1\'s in the window equals `k`, compare the current substring (`s[l:r+1]`) with the current best `min_str` and update it if it is shorter or lexicographically smaller.\n5. Shrink the window by moving the left pointer `l` and updating `count_ones` until the window no longer has exactly `k` \'1\'s.\n6. Repeat until all possible substrings are processed.\n7. Return the best substring `min_str` or an empty string if no valid substring exists.\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```python3 []\nclass Solution:\n    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n        min_str = ""\n        count_ones = l = r = 0\n        \n        while r < len(s):\n            # Increment count_ones if s[r] is \'1\'\n            count_ones += s[r] == \'1\'\n            \n            # Check if we have a valid substring\n            while count_ones == k:\n                cur_str = s[l:r + 1]\n                # Compare based on length and lexicographical order in one step\n                if not min_str or (len(cur_str), cur_str) < (len(min_str), min_str):\n                    min_str = cur_str\n                \n                # Move the left pointer and adjust count_ones\n                count_ones -= s[l] == \'1\'\n                l += 1\n            \n            # Move the right pointer\n            r += 1\n\n        return min_str\n\n```
['String', 'Sliding Window', 'Python3']