Video Solution(Brute->Optimal) 🔥 || Sliding Window 🔥 || C++,JAVA,PYTHON 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nTry to code brute force and observe whether we can optimize it or not.\nWhenever we fin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry to code brute force and observe whether we can optimize it or not.\nWhenever we find \'k\' or some condition to satify \'k\'. Try to think about sliding window or priority_queue. You will get some leads\n\n# ***Detailed and easy Video Solution***\n\nhttps://youtu.be/q7bEQMv9TFQ\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe code iterates through a string, counting \'1\'s until reaching the desired count, \'k\'. It then slides a window to find the shortest substring with \'k\' \'1\'s, updating the result string accordingly. It compares substrings by length and lexicographic order in the process.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(N+N)->O(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(N)\n\n# Brute Force\n```C++ []\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string s, int k) {\n        int n=s.size();\n        string ans;\n        int i=0,j=0;\n        int c=0;\n        while(j<n)\n        {\n            if(s[j]==\'1\')\n                c++;\n            if(c==k)\n            {   \n                while(i<n && c==k)\n                {\n                    string s1=s.substr(i,j-i+1);\n                    if(ans.size()==0 || s1.size()<ans.size())\n                        ans=s1;\n                    else if(s1.size()==ans.size())\n                        ans=min(ans,s1);\n                    if(s[i]==\'1\')\n                        c--;\n                    i++;\n                }\n            }\n            j++;\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution:\n    def shortestBeautifulSubstring(self, s, k):\n        n = len(s)\n        ans = ""\n        i = 0\n        j = 0\n        c = 0\n\n        while j < n:\n            if s[j] == \'1\':\n                c += 1\n            if c == k:\n                while i < n and c == k:\n                    s1 = s[i:j + 1]\n                    if not ans or len(s1) < len(ans):\n                        ans = s1\n                    elif len(s1) == len(ans):\n                        ans = min(ans, s1)\n                    if s[i] == \'1\':\n                        c -= 1\n                    i += 1\n            j += 1\n        return ans\n\n```\n```Java []\npublic class Solution {\n    public String shortestBeautifulSubstring(String s, int k) {\n        int n = s.length();\n        String ans = "";\n        int i = 0, j = 0;\n        int c = 0;\n        \n        while (j < n) {\n            if (s.charAt(j) == \'1\') {\n                c++;\n            }\n            if (c == k) {\n                while (i < n && c == k) {\n                    String s1 = s.substring(i, j + 1);\n                    if (ans.isEmpty() || s1.length() < ans.length()) {\n                        ans = s1;\n                    } else if (s1.length() == ans.length()) {\n                        ans = (ans.compareTo(s1) < 0) ? ans : s1;\n                    }\n                    if (s.charAt(i) == \'1\') {\n                        c--;\n                    }\n                    i++;\n                }\n            }\n            j++;\n        }\n        return ans;\n    }\n}\n\n```\n\n# Optimal Code\n```C++ []\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string s, int k) {\n        int n=s.size();\n        string ans;\n        int i=0,j=0;\n        int c=0;\n        while(j<n)\n        {\n            if(s[j]==\'1\')\n                c++;\n            if(c==k)\n            {   \n                while(i<n && c==k)\n                {\n                    string s1=s.substr(i,j-i+1);\n                    if(ans.size()==0 || s1.size()<ans.size())\n                        ans=s1;\n                    else if(s1.size()==ans.size())\n                        ans=min(ans,s1);\n                    if(s[i]==\'1\')\n                        c--;\n                    i++;\n                }\n            }\n            j++;\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution:\n    def shortestBeautifulSubstring(self, s, k):\n        n = len(s)\n        ans = ""\n        i = 0\n        j = 0\n        c = 0\n\n        while j < n:\n            if s[j] == \'1\':\n                c += 1\n            if c == k:\n                while i < n and c == k:\n                    s1 = s[i:j + 1]\n                    if not ans or len(s1) < len(ans):\n                        ans = s1\n                    elif len(s1) == len(ans):\n                        ans = min(ans, s1)\n                    if s[i] == \'1\':\n                        c -= 1\n                    i += 1\n                j += 1\n        return ans\n```\n```Java []\npublic class Solution {\n    public String shortestBeautifulSubstring(String s, int k) {\n        int n = s.length();\n        String ans = "";\n        int i = 0, j = 0;\n        int c = 0;\n        \n        while (j < n) {\n            if (s.charAt(j) == \'1\') {\n                c++;\n            }\n            if (c == k) {\n                while (i < n && c == k) {\n                    String s1 = s.substring(i, j + 1);\n                    if (ans.isEmpty() || s1.length() < ans.length()) {\n                        ans = s1;\n                    } else if (s1.length() == ans.length()) {\n                        ans = (ans.compareTo(s1) < 0) ? ans : s1;\n                    }\n                    if (s.charAt(i) == \'1\') {\n                        c--;\n                    }\n                    i++;\n                }\n            }\n            j++;\n        }\n        return ans;\n    }\n}\n```\n\n# ***If you like the solution Please Upvote and subscribe to my youtube channel***\n***It Motivates me to record more videos***\n\n*Thank you* \uD83D\uDE00
['String', 'Sliding Window', 'Python', 'C++', 'Java']