[LeetCode] Shortest and Lexicographically Smallest Beautiful String

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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];
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2023/10/15/PS/LeetCode/shortest-and-lexicographically-smallest-beautiful-string/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.