O(N) Time Complexity with C++
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string s, int k) {\n        string lsbs = ""; //Lexicographically smallest beautiful string\n        \n        vector<int> indx; //Array of Indexes where 1\'s has occured\n        int cnt=0; //Count of 1\'s\n\n        for(int i=0; i<s.size(); i++){\n            string bs = ""; // Beautiful Substring\n\n            if(s[i]==\'1\'){\n                cnt++;\n                indx.push_back(i);\n\n                if(cnt>=k){\n                    int si = indx[indx.size()-k]; // Stating index of the current Beautiful Substring (Explained below)\n                    bs = s.substr(si,i+1 - si); \n\n                    if(lsbs.size()==0) //If it\'s the first bs and lsbs is embty by now\n                        lsbs = s.substr(si, i+1-si);\n                    else if(lsbs.size()>bs.size()) // Checking if new sbs is smaller in size than lsbs\n                        lsbs = bs;\n                    else if(lsbs.size()==bs.size()) // If it\'s of equal size, we check lexicography\n                        lsbs = min(lsbs,bs);\n                }\n            }\n        }\n\n    return lsbs;\n    }\n};\n\n// #### bs = s.substr(indx[indx.size()-k],i+1);\n\n// - int ni = indx.size(); -----------------> Size of the Index\n// - indx.size()-k ------------------------> Index of Indx where the index of first 1 in s is stored\n// - i+1 ---------------------------------> Legths to be sliced\n// - indx[indx.size()-k],i+1)-------------> Index of s where first 1 is located (index of s) and from where the string will be sliced\n// - s.substr(indx[indx.size()-k],i) ------> Slicing a substring where it contains exactly one 1\n```
['C++']