2014. Longest Subsequence Repeated k Times Hard

1/**
2 * [2014] Longest Subsequence Repeated k Times
3 *
4 * You are given a string s of length n, and an integer k. You are tasked to find the longest subsequence repeated k times in string s.
5 * 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.
6 * A subsequence seq is repeated k times in the string s if seq * k is a subsequence of s, where seq * k represents a string constructed by concatenating seq k times.
7 * 
8 * 	For example, "bba" is repeated 2 times in the string "bababcba", because the string "bbabba", constructed by concatenating "bba" 2 times, is a subsequence of the string "<u>b</u>a<u>bab</u>c<u>ba</u>".
9 * 
10 * Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.
11 *  
12 * Example 1:
13 * <img alt="example 1" src="https://assets.leetcode.com/uploads/2021/08/30/longest-subsequence-repeat-k-times.png" style="width: 457px; height: 99px;" />
14 * Input: s = "letsleetcode", k = 2
15 * Output: "let"
16 * Explanation: There are two longest subsequences repeated 2 times: "let" and "ete".
17 * "let" is the lexicographically largest one.
18 * 
19 * Example 2:
20 * 
21 * Input: s = "bb", k = 2
22 * Output: "b"
23 * Explanation: The longest subsequence repeated 2 times is "b".
24 * 
25 * Example 3:
26 * 
27 * Input: s = "ab", k = 2
28 * Output: ""
29 * Explanation: There is no subsequence repeated 2 times. Empty string is returned.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	n == s.length
35 * 	2 <= n, k <= 2000
36 * 	2 <= n < k * 8
37 * 	s consists of lowercase English letters.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/longest-subsequence-repeated-k-times/
43// discuss: https://leetcode.com/problems/longest-subsequence-repeated-k-times/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn longest_subsequence_repeated_k(s: String, k: 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_2014() {
61    }
62}
63