2904. Shortest and Lexicographically Smallest Beautiful String

You are given a binary string s and a positive integer k.

A substring of s is beautiful if the number of 1‘s in it is exactly k.

Let len be the length of the shortest beautiful substring.

Return the lexicographically smallest beautiful substring of string s with length equal to len. If s doesn’t contain a beautiful substring, return an empty string.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

• For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        vector<int> at;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '1') at.push_back(i);
        }
        if(at.size() < k) return "";
        int len = 1e9;
        for(int i = k - 1; i < at.size(); i++) {
            len = min(len, at[i] - at[i-k+1] + 1);
        }
        vector<string> cand;
        for(int i = k - 1; i < at.size(); i++) {
            if(len !=  (at[i] - at[i-k+1] + 1)) continue;
            cand.push_back(s.substr(at[i-k+1],len));
        }
        sort(begin(cand), end(cand));
        return cand[0];
    }
};