2904. Shortest and Lexicographically Smallest Beautiful String Medium

1/**
2 * [2904] Shortest and Lexicographically Smallest Beautiful String
3 *
4 * You are given a binary string s and a positive integer k.
5 * A substring of s is beautiful if the number of 1's in it is exactly k.
6 * Let len be the length of the shortest beautiful substring.
7 * 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.
8 * 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.
9 * 
10 * 	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.
11 * 
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: s = "100011001", k = 3
16 * Output: "11001"
17 * Explanation: There are 7 beautiful substrings in this example:
18 * 1. The substring "<u>100011</u>001".
19 * 2. The substring "<u>1000110</u>01".
20 * 3. The substring "<u>10001100</u>1".
21 * 4. The substring "1<u>00011001</u>".
22 * 5. The substring "10<u>0011001</u>".
23 * 6. The substring "100<u>011001</u>".
24 * 7. The substring "1000<u>11001</u>".
25 * The length of the shortest beautiful substring is 5.
26 * The lexicographically smallest beautiful substring with length 5 is the substring "11001".
27 * 
28 * <strong class="example">Example 2:
29 * 
30 * Input: s = "1011", k = 2
31 * Output: "11"
32 * Explanation: There are 3 beautiful substrings in this example:
33 * 1. The substring "<u>101</u>1".
34 * 2. The substring "1<u>011</u>".
35 * 3. The substring "10<u>11</u>".
36 * The length of the shortest beautiful substring is 2.
37 * The lexicographically smallest beautiful substring with length 2 is the substring "11".
38 * 
39 * <strong class="example">Example 3:
40 * 
41 * Input: s = "000", k = 1
42 * Output: ""
43 * Explanation: There are no beautiful substrings in this example.
44 * 
45 *  
46 * Constraints:
47 * 
48 * 	1 <= s.length <= 100
49 * 	1 <= k <= s.length
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/shortest-and-lexicographically-smallest-beautiful-string/
55// discuss: https://leetcode.com/problems/shortest-and-lexicographically-smallest-beautiful-string/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
61        String::new()
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_2904() {
73    }
74}
75