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 lexicographicallysmallest beautiful substring of string _swith length equal tolen. If s doesn’t contain a beautiful substring, return anempty 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.
Input: s ="100011001", k =3Output: "11001"Explanation: There are 7 beautiful substrings inthis example:1. The substring "_100011_ 001".2. The substring "_1000110_ 01".3. The substring "_10001100_ 1".4. The substring "1 _00011001_ ".5. The substring "10 _0011001_ ".6. The substring "100 _011001_ ".7. The substring "1000 _11001_ ".The length of the shortest beautiful substring is5.The lexicographically smallest beautiful substring with length 5is the substring "11001".
Input: s ="1011", k =2Output: "11"Explanation: There are 3 beautiful substrings inthis example:1. The substring "_101_ 1".2. The substring "1 _011_ ".3. The substring "10 _11_ ".The length of the shortest beautiful substring is2.The lexicographically smallest beautiful substring with length 2is the substring "11".
We want the shortest substring with exactly k ‘1’s, and among those, the lexicographically smallest. We can use a sliding window to find all substrings with exactly k ‘1’s, track the minimum length, and then among those, pick the smallest lexicographically.
classSolution {
public: string shortestBeautifulSubstring(string s, int k) {
int n = s.size(), cnt =0, l =0, minLen = n +1;
string ans ="";
for (int r =0; r < n; ++r) {
if (s[r] =='1') ++cnt;
while (cnt > k) {
if (s[l++] =='1') --cnt;
}
if (cnt == k) {
while (s[l] !='1') ++l;
int len = r - l +1;
string sub = s.substr(l, len);
if (len < minLen || (len == minLen && sub < ans)) {
minLen = len;
ans = sub;
}
}
}
return ans;
}
};
classSolution {
public String shortestBeautifulSubstring(String s, int k) {
int n = s.length(), cnt = 0, l = 0, minLen = n + 1;
String ans ="";
for (int r = 0; r < n; ++r) {
if (s.charAt(r) =='1') ++cnt;
while (cnt > k) {
if (s.charAt(l++) =='1') --cnt;
}
if (cnt == k) {
while (s.charAt(l) !='1') ++l;
int len = r - l + 1;
String sub = s.substring(l, r + 1);
if (len < minLen || (len == minLen && sub.compareTo(ans) < 0)) {
minLen = len;
ans = sub;
}
}
}
return ans;
}
}
classSolution {
funshortestBeautifulSubstring(s: String, k: Int): String {
val n = s.length
var cnt = 0var l = 0var minLen = n + 1var ans = ""for (r in0 until n) {
if (s[r] =='1') cnt++while (cnt > k) {
if (s[l++] =='1') cnt-- }
if (cnt == k) {
while (s[l] !='1') l++val len = r - l + 1val sub = s.substring(l, r + 1)
if (len < minLen || (len == minLen && sub < ans)) {
minLen = len
ans = sub
}
}
}
return ans
}
}
classSolution:
defshortestBeautifulSubstring(self, s: str, k: int) -> str:
n = len(s)
cnt = l =0 min_len = n +1 ans =''for r in range(n):
if s[r] =='1':
cnt +=1while cnt > k:
if s[l] =='1':
cnt -=1 l +=1if cnt == k:
while s[l] !='1':
l +=1 length = r - l +1 sub = s[l:r+1]
if length < min_len or (length == min_len and (ans ==''or sub < ans)):
min_len = length
ans = sub
return ans
impl Solution {
pubfnshortest_beautiful_substring(s: String, k: i32) -> String {
let s = s.as_bytes();
let n = s.len();
letmut cnt =0;
letmut l =0;
letmut min_len = n +1;
letmut ans = String::new();
for r in0..n {
if s[r] ==b'1' { cnt +=1; }
while cnt > k {
if s[l] ==b'1' { cnt -=1; }
l +=1;
}
if cnt == k {
while s[l] !=b'1' { l +=1; }
let len = r - l +1;
let sub =&s[l..=r];
let sub_str = String::from_utf8(sub.to_vec()).unwrap();
if len < min_len || (len == min_len && (ans.is_empty() || sub_str < ans)) {
min_len = len;
ans = sub_str;
}
}
}
ans
}
}