2901. Longest Unequal Adjacent Groups Subsequence II Medium

1/**
2 * [2901] Longest Unequal Adjacent Groups Subsequence II
3 *
4 * You are given a string array words, and an array groups, both arrays having length n.
5 * The hamming distance between two strings of equal length is the number of positions at which the corresponding characters are different.
6 * You need to select the longest <span data-keyword="subsequence-array">subsequence</span> from an array of indices [0, 1, ..., n - 1], such that for the subsequence denoted as [i0, i1, ..., ik-1] having length k, the following holds:
7 * 
8 * 	For adjacent indices in the subsequence, their corresponding groups are unequal, i.e., groups[ij] != groups[ij+1], for each j where 0 < j + 1 < k.
9 * 	words[ij] and words[ij+1] are equal in length, and the hamming distance between them is 1, where 0 < j + 1 < k, for all indices in the subsequence.
10 * 
11 * Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.
12 * Note: strings in words may be unequal in length.
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
16 * Input: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">words = ["bab","dab","cab"], groups = [1,2,2]</span>
17 * Output: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">["bab","cab"]</span>
18 * Explanation: A subsequence that can be selected is [0,2].
19 * 
20 * 	groups[0] != groups[2]
21 * 	words[0].length == words[2].length, and the hamming distance between them is 1.
22 * 
23 * So, a valid answer is [words[0],words[2]] = ["bab","cab"].
24 * Another subsequence that can be selected is [0,1].
25 * 
26 * 	groups[0] != groups[1]
27 * 	words[0].length == words[1].length, and the hamming distance between them is 1.
28 * 
29 * So, another valid answer is [words[0],words[1]] = ["bab","dab"].
30 * It can be shown that the length of the longest subsequence of indices that satisfies the conditions is 2.
31 * </div>
32 * <strong class="example">Example 2:
33 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
34 * Input: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">words = ["a","b","c","d"], groups = [1,2,3,4]</span>
35 * Output: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">["a","b","c","d"]</span>
36 * Explanation: We can select the subsequence [0,1,2,3].
37 * It satisfies both conditions.
38 * Hence, the answer is [words[0],words[1],words[2],words[3]] = ["a","b","c","d"].
39 * It has the longest length among all subsequences of indices that satisfy the conditions.
40 * Hence, it is the only answer.
41 * </div>
42 *  
43 * Constraints:
44 * 
45 * 	1 <= n == words.length == groups.length <= 1000
46 * 	1 <= words[i].length <= 10
47 * 	1 <= groups[i] <= n
48 * 	words consists of distinct strings.
49 * 	words[i] consists of lowercase English letters.
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/longest-unequal-adjacent-groups-subsequence-ii/
55// discuss: https://leetcode.com/problems/longest-unequal-adjacent-groups-subsequence-ii/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn get_words_in_longest_subsequence(words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
61        vec![]
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_2901() {
73    }
74}
75