✅☑[C++/C/Java/Python/JavaScript] || Beats 100% || 2 Appraoches || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n #### Approach 1 (Brute Force)\n\n1. The function iterates through all poss
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n #### ***Approach 1 (Brute Force)***\n\n1. The function iterates through all possible substrings and counts the number of ones (\'1\') in each substring.\n1. It first finds all substrings with exactly \'k\' ones to determine the minimum length required.\n1. If a valid substring is found, it updates the \'len\' variable.\n1. If no valid substring is found (len remains very large), it returns an empty string.\n1. Then, it iterates again to find all substrings with both \'len\' and \'k\' ones.\nValid substrings are added to the \'v\' vector.\n1. Finally, it sorts the valid substrings lexicographically and returns the lexicographically smallest one.\n\n\n# Complexity\n- *Time complexity:*\n   $$O(n^3)$$\n    \n\n- *Space complexity:*\n   $$O(1e8)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string s, int k) {\n        int n = s.length(); // Get the length of the input string.\n        int len = 1e9; // Initialize \'len\' to a large value.\n\n        // First, find all substrings with exactly \'k\' ones.\n        for (int i = 0; i < n; i++) {\n            for (int j = i; j < n; j++) {\n                string str;\n                int l = 0; // Initialize the count of ones in the substring \'str\'.\n                for (int k = i; k <= j; k++) {\n                    if (s[k] == \'1\') l++; // Count ones and construct the substring \'str\'.\n                    str += s[k];\n                }\n                if (l == k) len = min(len, j - i + 1); // If \'str\' has \'k\' ones, update \'len\'.\n            }\n        }\n        vector<string> v;\n\n        if (len > 1e8) return string(); // If no valid substring found, return an empty string.\n\n        // Now, find substrings with \'len\' and \'k\' ones.\n        for (int i = 0; i < n; i++) {\n            for (int j = i; j < n; j++) {\n                string str;\n                int l = 0; // Initialize the count of ones in the substring \'str\'.\n                for (int k = i; k <= j; k++) {\n                    if (s[k] == \'1\') l++; // Count ones and construct the substring \'str\'.\n                    str += s[k];\n                }\n                if (l == k && j - i + 1 == len) v.push_back(str); // If \'str\' meets the criteria, add it to \'v\'.\n            }\n        }\n\n        sort(v.begin(), v.end()); // Sort the valid substrings lexicographically.\n        return v[0]; // Return the lexicographically smallest valid substring.\n    }\n};\n\n\n```\n\n```C []\n\n#include <string.h>\n\nchar *shortestBeautifulSubstring(char *s, int k) {\n    int n = strlen(s);\n    int len = 1e9;\n    int start = -1;\n    int end = -1;\n\n    // First, find all substrings with exactly \'k\' ones.\n    for (int i = 0; i < n; i++) {\n        for (int j = i; j < n; j++) {\n            int ones = 0;\n            for (int l = i; l <= j; l++) {\n                if (s[l] == \'1\') ones++;\n            }\n            if (ones == k && j - i + 1 < len) {\n                len = j - i + 1;\n                start = i;\n                end = j;\n            }\n        }\n    }\n\n    if (len > 1e8) return "";\n\n    char *result = (char *)malloc(len + 1);\n    for (int i = start; i <= end; i++) {\n        result[i - start] = s[i];\n    }\n    result[len] = \'\\0\';\n\n    return result;\n}\n\n\n```\n\n```Java []\npublic String shortestBeautifulSubstring(String s, int k) {\n    int n = s.length();\n    int len = 1e9;\n    int start = -1;\n    int end = -1;\n\n    // First, find all substrings with exactly \'k\' ones.\n    for (int i = 0; i < n; i++) {\n        for (int j = i; j < n; j++) {\n            int ones = 0;\n            for (int l = i; l <= j; l++) {\n                if (s.charAt(l) == \'1\') ones++;\n            }\n            if (ones == k && j - i + 1 < len) {\n                len = j - i + 1;\n                start = i;\n                end = j;\n            }\n        }\n    }\n\n    if (len > 1e8) return "";\n\n    return s.substring(start, end + 1);\n}\n\n\n```\n\n```python3 []\nclass Solution:\n    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n        n = len(s)\n        len_min = 1e9\n        start, end = -1, -1\n\n        # First, find all substrings with exactly \'k\' ones.\n        for i in range(n):\n            for j in range(i, n):\n                ones = 0\n                for l in range(i, j + 1):\n                    if s[l] == \'1\':\n                        ones += 1\n                if ones == k and j - i + 1 < len_min:\n                    len_min = j - i + 1\n                    start, end = i, j\n\n        if len_min > 1e8:\n            return ""\n\n        return s[start:end + 1]\n\n\n```\n\n```javascript []\nvar shortestBeautifulSubstring = function(s, k) {\n    var n = s.length;\n    var len = 1e9;\n    var start = -1;\n    var end = -1;\n\n    // First, find all substrings with exactly \'k\' ones.\n    for (var i = 0; i < n; i++) {\n        for (var j = i; j < n; j++) {\n            var ones = 0;\n            for (var l = i; l <= j; l++) {\n                if (s[l] === \'1\') ones++;\n            }\n            if (ones === k && j - i + 1 < len) {\n                len = j - i + 1;\n                start = i;\n                end = j;\n            }\n        }\n    }\n\n    if (len > 1e8) return "";\n\n    return s.substring(start, end + 1);\n};\n\n```\n\n\n---\n#### ***Approach 2 (Optimized)***\n1. Initialize variables: `i` and `j` are pointers used to represent the current substring, `cnt` is used to count the number of \'1\'s in the current substring, and `ans` is used to store the shortest valid substring.\n\n1. Iterate through the string `s` using the `j` pointer to expand the right side of the current substring.\n\n1. When a `1` is encountered at `s[j]`, increment the cnt.\n\n1. Check if `cnt` is equal to `k`. When `cnt` reaches `k`, it means we have found a substring with at least `k` \'1\'s.\n\n1. Use the `i` pointer to shrink the left side of the substring while keeping track of valid substrings:\n\n  - Create a temporary string `temp` using `s.substr(i, j - i + 1)` to represent the current valid substring.\n  - Check if `ans` is empty (indicating it\'s the first valid substring found) or if the size of `temp` is smaller than the current `ans`. If so, update `ans` with `temp`.\n  - If the sizes of `ans` and `temp` are the same, choose the lexicographically smaller one using the `min` function.\n1. Continue moving the `i` pointer to find other valid substrings. When a `1` is encountered at `s[i]`, decrement the `cnt`.\n\n1. Continue to increment the `j` pointer to explore more substrings.\n\n1. After the loop, `ans` will contain the shortest valid substring.\n\n\n# Complexity\n- *Time complexity:*\n   $$O(n)$$\n    \n\n- *Space complexity:*\n   $$O(1)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string s, int k) {\n        int n = s.size(); // Get the length of the input string.\n        int i = 0, j = 0; // Initialize pointers for the substring.\n        int cnt = 0; // Initialize a count of \'1\'s in the current substring.\n        string ans; // Initialize the result string.\n\n        while (j < n) {\n            if (s[j] == \'1\') cnt++; // If \'1\' is encountered, increment the count.\n\n            if (cnt == k) { // When the count reaches \'k\', it\'s a valid substring.\n                while (i < n && cnt == k) {\n                    string temp = s.substr(i, j - i + 1); // Extract the current substring.\n                    if (ans.size() == 0 || ans.size() > temp.size()) {\n                        ans = temp; // If result is empty or longer, update the result.\n                    }\n                    else if (ans.size() == temp.size()) {\n                        ans = min(ans, temp); // Choose the lexicographically smaller substring.\n                    }\n\n                    if (s[i] == \'1\') cnt--; // When \'1\' is encountered on the left, decrement the count.\n                    i++;\n                }\n            }\n            j++;\n        }\n        return ans; // Return the shortest valid substring.\n    }\n};\n\n\n```\n\n```C []\n\n#include <stdio.h>\n#include <string.h>\n\nchar* shortestBeautifulSubstring(char* s, int k) {\n    int n = strlen(s); // Get the length of the input string.\n    int i = 0, j = 0; // Initialize pointers for the substring.\n    int cnt = 0; // Initialize a count of \'1\'s in the current substring.\n    char* ans = NULL; // Initialize the result string.\n\n    while (j < n) {\n        if (s[j] == \'1\') cnt++; // If \'1\' is encountered, increment the count.\n\n        if (cnt == k) { // When the count reaches \'k\', it\'s a valid substring.\n            while (i < n && cnt == k) {\n                char temp[j - i + 2]; // Create a temporary substring.\n                strncpy(temp, &s[i], j - i + 1);\n                temp[j - i + 1] = \'\\0\'; // Null-terminate the temporary substring.\n\n                if (!ans || strlen(ans) > strlen(temp)) {\n                    if (ans) free(ans); // Free the previous result.\n                    ans = (char*)malloc(strlen(temp) + 1); // Allocate memory for the result.\n                    strcpy(ans, temp); // Copy the temporary substring to the result.\n                } else if (strlen(ans) == strlen(temp)) {\n                    ans = (strcmp(ans, temp) > 0) ? temp : ans; // Choose the lexicographically smaller substring.\n                }\n\n                if (s[i] == \'1\') cnt--; // When \'1\' is encountered on the left, decrement the count.\n                i++;\n            }\n        }\n        j++;\n    }\n    return ans;\n}\n\n\n```\n\n```Java []\n\nclass Solution {\n    public String shortestBeautifulSubstring(String s, int k) {\n        int n = s.length();\n        int i = 0, j = 0;\n        int cnt = 0;\n        String ans = "";\n\n        while (j < n) {\n            if (s.charAt(j) == \'1\') {\n                cnt++;\n            }\n\n            if (cnt == k) {\n                while (i < n && cnt == k) {\n                    String temp = s.substring(i, j + 1);\n                    if (ans.isEmpty() || ans.length() > temp.length()) {\n                        ans = temp;\n                    } else if (ans.length() == temp.length()) {\n                        ans = ans.compareTo(temp) < 0 ? ans : temp;\n                    }\n\n                    if (s.charAt(i) == \'1\') {\n                        cnt--;\n                    }\n                    i++;\n                }\n            }\n            j++;\n        }\n        return ans;\n    }\n}\n\n\n```\n\n```python3 []\nclass Solution:\n    def shortestBeautifulSubstring(self, s: str, k: int) -> str:\n        n = len(s)\n        i = 0\n        j = 0\n        cnt = 0\n        ans = ""\n\n        while j < n:\n            if s[j] == \'1\':\n                cnt += 1\n\n            if cnt == k:\n                while i < n and cnt == k:\n                    temp = s[i:j + 1]\n                    if not ans or len(ans) > len(temp):\n                        ans = temp\n                    elif len(ans) == len(temp):\n                        ans = min(ans, temp)\n\n                    if s[i] == \'1\':\n                        cnt -= 1\n                    i += 1\n\n            j += 1\n\n        return ans\n\n\n```\n\n```javascript []\nvar shortestBeautifulSubstring = function (s, k) {\n    let n = s.length;\n    let i = 0;\n    let j = 0;\n    let cnt = 0;\n    let ans = "";\n\n    while (j < n) {\n        if (s[j] === \'1\') {\n            cnt++;\n        }\n\n        if (cnt === k) {\n            while (i < n && cnt === k) {\n                let temp = s.substring(i, j + 1);\n                if (!ans || ans.length > temp.length) {\n                    ans = temp;\n                } else if (ans.length === temp.length) {\n                    ans = ans < temp ? ans : temp;\n                }\n\n                if (s[i] === \'1\') {\n                    cnt--;\n                }\n                i++;\n            }\n        }\n        j++;\n    }\n\n    return ans;\n};\n\n\n```\n\n\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['String', 'C', 'Sorting', 'String Matching', 'C++', 'Java', 'Python3', 'JavaScript']