3302. Find the Lexicographically Smallest Valid Sequence Medium

1/**
2 * [3302] Find the Lexicographically Smallest Valid Sequence
3 *
4 * You are given two strings word1 and word2.
5 * A string x is called almost equal to y if you can change at most one character in x to make it identical to y.
6 * A sequence of indices seq is called valid if:
7 * 
8 * 	The indices are sorted in ascending order.
9 * 	Concatenating the characters at these indices in word1 in the same order results in a string that is almost equal to word2.
10 * 
11 * Return an array of size word2.length representing the <span data-keyword="lexicographically-smaller-array">lexicographically smallest</span> valid sequence of indices. If no such sequence of indices exists, return an empty array.
12 * Note that the answer must represent the lexicographically smallest array, not the corresponding string formed by those indices.<!-- notionvc: 2ff8e782-bd6f-4813-a421-ec25f7e84c1e -->
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">word1 = "vbcca", word2 = "abc"</span>
17 * Output: <span class="example-io">[0,1,2]</span>
18 * Explanation:
19 * The lexicographically smallest valid sequence of indices is [0, 1, 2]:
20 * 
21 * 	Change word1[0] to 'a'.
22 * 	word1[1] is already 'b'.
23 * 	word1[2] is already 'c'.
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block">
27 * Input: <span class="example-io">word1 = "bacdc", word2 = "abc"</span>
28 * Output: <span class="example-io">[1,2,4]</span>
29 * Explanation:
30 * The lexicographically smallest valid sequence of indices is [1, 2, 4]:
31 * 
32 * 	word1[1] is already 'a'.
33 * 	Change word1[2] to 'b'.
34 * 	word1[4] is already 'c'.
35 * </div>
36 * <strong class="example">Example 3:
37 * <div class="example-block">
38 * Input: <span class="example-io">word1 = "aaaaaa", word2 = "aaabc"</span>
39 * Output: <span class="example-io">[]</span>
40 * Explanation:
41 * There is no valid sequence of indices.
42 * </div>
43 * <strong class="example">Example 4:
44 * <div class="example-block">
45 * Input: <span class="example-io">word1 = "abc", word2 = "ab"</span>
46 * Output: <span class="example-io">[0,1]</span>
47 * </div>
48 *  
49 * Constraints:
50 * 
51 * 	1 <= word2.length < word1.length <= 3 * 10^5
52 * 	word1 and word2 consist only of lowercase English letters.
53 * 
54 */
55pub struct Solution {}
56
57// problem: https://leetcode.com/problems/find-the-lexicographically-smallest-valid-sequence/
58// discuss: https://leetcode.com/problems/find-the-lexicographically-smallest-valid-sequence/discuss/?currentPage=1&orderBy=most_votes&query=
59
60// submission codes start here
61
62impl Solution {
63    pub fn valid_sequence(word1: String, word2: String) -> Vec<i32> {
64        vec![]
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_3302() {
76    }
77}
78