Iterative Greedy Solution (56ms)
Approach\n1. For each index/suffix in word2 identify and store last opportunity in word1 (i.e. biggest index) to match the word1 suffix to word2 suffix.\n2. Ite
# Approach\n1. For each index/suffix in word2 identify and store last opportunity in word1 (i.e. biggest index) to match the word1 suffix to word2 suffix.\n2. Iterate through word1 while keeping track if the 1-time allowed deviation has been used. In case of match iterate both pointers in word1 and word2 and append word1 pointer to the resulting sequence. In case 1-time allowed deviation has not been used, also increment both pointers and append first pointer to the resulting sequence. However in this case it needs to be checked that pointer1 has not exceeded the last opportunity identified in step 1 or that there\'s no more character in word2 to match.\n\n# Complexity\n- Time complexity: O(n) with n = length of word1\n- Space complexity: O(m) with m = length of word2\n\n# Code\n```rust []\nimpl Solution {\n    pub fn valid_sequence(word1: String, word2: String) -> Vec<i32> {\n        //find last chance of an index in word1 to match a index in word2\n        let mut last: Vec<usize> = vec![0; word2.len()];\n        let mut i2: usize = word2.len() - 1;\n        for i1 in (0..word1.len()).rev() {\n            if i2 >= 0 && word1.bytes().nth(i1) == word2.bytes().nth(i2) {\n                last[i2] = i1;\n                i2 -= 1;\n            }\n        }\n\n        //find the subsequence of indices in word1\n        let mut res: Vec<i32> = vec![-1; word2.len()];\n        let mut changed: bool = false;\n        i2 = 0;\n        for i1 in (0..word1.len()) {\n            if word1.bytes().nth(i1) == word2.bytes().nth(i2) || (!changed && (i2 == word2.len() - 1 || i1 < last[i2 + 1])) {\n                res[i2] = i1 as i32;\n                changed |= word1.bytes().nth(i1) != word2.bytes().nth(i2);\n                i2 += 1;\n                if i2 >= word2.len() { break; }\n            }\n        }\n        if i2 < word2.len() { return vec![]; }\n        res\n    }\n}\n```
['Rust']