2030. Smallest K-Length Subsequence With Occurrences of a Letter Hard

1/**
2 * [2030] Smallest K-Length Subsequence With Occurrences of a Letter
3 *
4 * You are given a string s, an integer k, a letter letter, and an integer repetition.
5 * Return the lexicographically smallest subsequence of s of length k that has the letter letter appear at least repetition times. The test cases are generated so that the letter appears in s at least repetition times.
6 * A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
7 * A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
8 *  
9 * Example 1:
10 * 
11 * Input: s = "leet", k = 3, letter = "e", repetition = 1
12 * Output: "eet"
13 * Explanation: There are four subsequences of length 3 that have the letter 'e' appear at least 1 time:
14 * - "lee" (from "<u>lee</u>t")
15 * - "let" (from "<u>le</u>e<u>t</u>")
16 * - "let" (from "<u>l</u>e<u>et</u>")
17 * - "eet" (from "l<u>eet</u>")
18 * The lexicographically smallest subsequence among them is "eet".
19 * 
20 * Example 2:
21 * <img alt="example-2" src="https://assets.leetcode.com/uploads/2021/09/13/smallest-k-length-subsequence.png" style="width: 339px; height: 67px;" />
22 * Input: s = "leetcode", k = 4, letter = "e", repetition = 2
23 * Output: "ecde"
24 * Explanation: "ecde" is the lexicographically smallest subsequence of length 4 that has the letter "e" appear at least 2 times.
25 * 
26 * Example 3:
27 * 
28 * Input: s = "bb", k = 2, letter = "b", repetition = 2
29 * Output: "bb"
30 * Explanation: "bb" is the only subsequence of length 2 that has the letter "b" appear at least 2 times.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= repetition <= k <= s.length <= 5 * 10^4
36 * 	s consists of lowercase English letters.
37 * 	letter is a lowercase English letter, and appears in s at least repetition times.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/
43// discuss: https://leetcode.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn smallest_subsequence(s: String, k: i32, letter: char, repetition: i32) -> String {
49        String::new()
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_2030() {
61    }
62}
63