3485. Longest Common Prefix of K Strings After Removal Hard

1/**
2 * [3485] Longest Common Prefix of K Strings After Removal
3 *
4 * You are given an array of strings words and an integer k.
5 * For each index i in the range [0, words.length - 1], find the length of the longest common <span data-keyword="string-prefix">prefix</span> among any k strings (selected at distinct indices) from the remaining array after removing the i^th element.
6 * Return an array answer, where answer[i] is the answer for i^th element. If removing the i^th element leaves the array with fewer than k strings, answer[i] is 0.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">words = ["jump","run","run","jump","run"], k = 2</span>
11 * Output: <span class="example-io">[3,4,4,3,4]</span>
12 * Explanation:
13 * 
14 * 	Removing index 0 ("jump"):
15 * 	
16 * 		words becomes: ["run", "run", "jump", "run"]. "run" occurs 3 times. Choosing any two gives the longest common prefix "run" (length 3).
17 * 	
18 * 	
19 * 	Removing index 1 ("run"):
20 * 	
21 * 		words becomes: ["jump", "run", "jump", "run"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).
22 * 	
23 * 	
24 * 	Removing index 2 ("run"):
25 * 	
26 * 		words becomes: ["jump", "run", "jump", "run"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).
27 * 	
28 * 	
29 * 	Removing index 3 ("jump"):
30 * 	
31 * 		words becomes: ["jump", "run", "run", "run"]. "run" occurs 3 times. Choosing any two gives the longest common prefix "run" (length 3).
32 * 	
33 * 	
34 * 	Removing index 4 ("run"):
35 * 	
36 * 		words becomes: ["jump", "run", "run", "jump"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).
37 * 	
38 * 	
39 * </div>
40 * <strong class="example">Example 2:
41 * <div class="example-block">
42 * Input: <span class="example-io">words = ["dog","racer","car"], k = 2</span>
43 * Output: <span class="example-io">[0,0,0]</span>
44 * Explanation:
45 * 
46 * 	Removing any index results in an answer of 0.
47 * </div>
48 *  
49 * Constraints:
50 * 
51 * 	1 <= k <= words.length <= 10^5
52 * 	1 <= words[i].length <= 10^4
53 * 	words[i] consists of lowercase English letters.
54 * 	The sum of words[i].length is smaller than or equal 10^5.
55 * 
56 */
57pub struct Solution {}
58
59// problem: https://leetcode.com/problems/longest-common-prefix-of-k-strings-after-removal/
60// discuss: https://leetcode.com/problems/longest-common-prefix-of-k-strings-after-removal/discuss/?currentPage=1&orderBy=most_votes&query=
61
62// submission codes start here
63
64impl Solution {
65    pub fn longest_common_prefix(words: Vec<String>, k: i32) -> Vec<i32> {
66        vec![]
67    }
68}
69
70// submission codes end
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_3485() {
78    }
79}
80