Why not not bit-mask O(N) solution?
Intuition\nMy initial approach to this problem utilized the following idea:\n- If we have two valid binary substrings s1 and s2, we can convert these to integer
# Intuition\nMy initial approach to this problem utilized the following idea:\n- If we have two valid binary substrings s1 and s2, we can convert these to integers and compare them directly to figure out what is the best solution. If int(s1) < int(s2) then s1 is the most beautiful substring.\n\nUsing this idea, I tried to device a O(N) sliding window solution, which kept track of current substring as a bit mask (essentially an integer) and checked if current substring is a better solution than previous solution using a simple integer comparison (O(1)) rather than slicing string (O(N))\n\nThis approach has limitations, and isn\'t really O(N):\n- a << b, which is used to maintain window mask at end of every loop iteration, is not an O(1) operation\n- Substring can be greater than 64bits, which is the largest size integer most languages/CPUs allow you to handle.\n\n\n# Sliding window bit mask - Bad\n\n```\n    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n        l, window_mask, ans_mask = 0, 0, float("inf")\n\n        for r in range(len(s)):\n            window_mask <<= 1\n            window_mask += int(s[r])\n            k -= int(s[r])\n\n            while k == 0:\n                if window_mask <= ans_mask:\n                    ans_mask = window_mask\n  \n                k += int(s[l])\n                window_mask -= int(s[l]) << (r-l)\n                l += 1\n\n        return bin(ans_mask)[2:] if ans_mask != float("inf") else ""\n```\n\n# Sliding window - Time O(N^2)\n```\nclass Solution:\n    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n        ans_l, ans_r = float("-inf"), float("inf")\n        l = 0\n        for r in range(len(s)):\n            k -= int(s[r])\n\n            while k == 0:\n                if r-l < ans_r-ans_l or (r-l == ans_r-ans_l and int(s[l:r+1], 2) < int(s[ans_l:ans_r+1], 2)):\n                    ans_r, ans_l = r, l\n                k += int(s[l])\n                l += 1\n        \n        return s[ans_l:ans_r+1] if ans_r != float("inf") else ""\n```
['Python3']