#2904
Shortest and Lexicographically Smallest Beautiful String
expert · 1005 · lc medium +32 · verified · 40.9% accepted · 204 likes · top 21%
Description
A binary string s and a positive integer k are given.
A substring is beautiful if it contains exactly k ones. Let len be the length of the shortest beautiful substring.
Return the lexicographically smallest beautiful substring of length len, or an empty string if no beautiful substring exists.
A string a is lexicographically greater than b (same length) if at the first differing position a has a larger character.
Example 1:
Input: s = "100011001", k = 3
Output: "11001"
Explanation: There are 7 beautiful substrings in this example:
1. The substring "100011001".
2. The substring "100011001".
3. The substring "100011001".
4. The substring "100011001".
5. The substring "100011001".
6. The substring "100011001".
7. The substring "100011001".
The length of the shortest beautiful substring is 5.
The lexicographically smallest beautiful substring with length 5 is the substring "11001".
Example 2:
Input: s = "1011", k = 2
Output: "11"
Explanation: There are 3 beautiful substrings in this example:
1. The substring "1011".
2. The substring "1011".
3. The substring "1011".
The length of the shortest beautiful substring is 2.
The lexicographically smallest beautiful substring with length 2 is the substring "11".
Example 3:
Input: s = "000", k = 1
Output: ""
Explanation: There are no beautiful substrings in this example.
Code
1
2
3