2904: Shortest and Lexicographically smallest beautiful string
Intuition\n Describe your first thoughts on how to solve this problem. \nBasic intuition after reading the problem is that we\'ll have to check for substrings u
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBasic intuition after reading the problem is that we\'ll have to check for substrings usign the sliding window or two pointer approach as to get the smallest length of substring with the constraint to find the k number of 1s.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFollowed the below mentioned steps:\n- Find the indexes where "1" is stored in the string and stored in a list\n-  Traverse through the list with the sliding window of size k\n    - Evauate the length of the substring by taking difference between indexes available at start and end of current window\n    - If this length being the least out the currently evaluated windows, then store it in a result list\n    - Else move to next window\n- At the end, sort the result list in ascending order and return the first substring from the result list\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def shortestBeautifulSubstring(self, s, k):\n        """\n        :type s: str\n        :type k: int\n        :rtype: str\n        """\n        l = []\n        for i in range(len(s)):\n            if s[i] == "1":\n                d[i] = s[i]\n                l.append(i)\n\n        if len(l) == 0 or len(l) < k:\n            return ""\n\n        min_length = len(s)\n        result = []\n\n        for i in range(len(l) - k + 1):\n            if min_length > (l[i+k-1] - l[i] + 1):\n                min_length = l[i+k-1] - l[i] + 1\n                result = []\n            elif min_length < (l[i+k-1] - l[i] + 1):\n                continue\n\n            result.append(s[l[i]:l[i+k-1]+1])\n\n        result.sort()\n        if result[0].count("1") == k:\n            return result[0]\n        else:\n            return ""\n            \n                    \n```
['Python']