Shortest Beautiful Substring with K Ones
IntuitionWe need to find the shortest substring of s that contains exactly k ones ('1').
If multiple substrings have the same minimum length, return the lexicog
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We need to find the shortest substring of s that contains exactly k ones ('1').

1. If multiple substrings have the same minimum length, return the lexicographically smallest one.
2. If no valid substring exists, return an empty string.
Since we are dealing with substring length and ones count, a sliding window approach is well-suited for this problem.


# Approach
<!-- Describe your approach to solving the problem. -->
1. Sliding Window Technique:

Use two pointers: l (left) and r (right) to maintain a valid window.
Expand r to include more characters and count ones ('1').
Once we have exactly k ones, we process the window:
If the length is smaller than the shortest found, reset the answer list.
If the length is the same as the shortest found, add to the answer list.
Move l forward to shrink the window while maintaining the k ones condition.
2. Sorting for Lexicographical Order:

Since multiple substrings may have the same shortest length, sort them to find the smallest one.
3. Edge Case Handling:

If no substring meets the condition, return "".
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Sliding Window Traversal: 𝑂(𝑛)Sorting (worst case): 𝑂(𝑚log𝑚), where 𝑚 is the number of substrings stored.
Total Complexity: 𝑂(𝑛+𝑚log𝑚) (usually 𝑂(𝑛) in practice since m is small).

# Code
```cpp []
class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int l = 0, r = 0;
        int onesCount = 0;
        int shortestLength = INT_MAX;
        int startIndex = -1;
        vector<string> ans;
        while (r < s.length()) {
            if (s[r] == '1') {
                onesCount++;
            }
            while (onesCount == k) {
                if (r - l + 1 <= shortestLength) {
                    if (r - l + 1 < shortestLength) {
                        ans.clear();  // Start a new set of substrings if shorter
                    }
                    shortestLength = r - l + 1;
                    startIndex = l;
                    ans.push_back(s.substr(startIndex, shortestLength));
                }
                if (s[l] == '1') {
                    onesCount--;
                }
                l++;
            }
            r++;
        }
        if (startIndex == -1) {
            return "";
        }
        sort(ans.begin(), ans.end());
        for (int i = 0; i < ans.size(); i++) {
            if (ans[i].length() == shortestLength) {
                return ans[i];
            }
        }
        return "";
    }
};
```
['String', 'Sliding Window', 'C++']