2273. Find Resultant Array After Removing Anagrams Easy

1/**
2 * [2273] Find Resultant Array After Removing Anagrams
3 *
4 * You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.
5 * In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i]
6 * are anagrams, and delete words[i] from words. Keep performing this operation as long as you can
7 * select an index that satisfies the conditions.
8 * Return words after performing all operations. It can be shown that selecting the indices for
9 * each operation in any arbitrary order will lead to the same result.
10 * An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase
11 * using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".
12 *  
13 * Example 1:
14 *
15 * Input: words = ["abba","baba","bbaa","cd","cd"]
16 * Output: ["abba","cd"]
17 * Explanation:
18 * One of the ways we can obtain the resultant array is by using the following operations:
19 * - Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2].
20 *   Now words = ["abba","baba","cd","cd"].
21 * - Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1].
22 *   Now words = ["abba","cd","cd"].
23 * - Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2].
24 *   Now words = ["abba","cd"].
25 * We can no longer perform any operations, so ["abba","cd"] is the final answer.
26 * Example 2:
27 *
28 * Input: words = ["a","b","c","d","e"]
29 * Output: ["a","b","c","d","e"]
30 * Explanation:
31 * No two adjacent strings in words are anagrams of each other, so no operations are performed.
32 *  
33 * Constraints:
34 *
35 * 1 <= words.length <= 100
36 * 1 <= words[i].length <= 10
37 * words[i] consists of lowercase English letters.
38 *
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/find-resultant-array-after-removing-anagrams/
43// discuss: https://leetcode.com/problems/find-resultant-array-after-removing-anagrams/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn remove_anagrams(words: Vec<String>) -> Vec<String> {
49        let mut result = words.clone();
50
51        let mut i = 0;
52
53        while i < result.len() - 1 {
54            if Self::is_anagram(&result[i], &result[i + 1]) {
55                result.remove(i + 1);
56            } else {
57                i += 1;
58            }
59        }
60
61        result
62    }
63
64    fn is_anagram(a: &String, b: &String) -> bool {
65        let mut va = vec![0; 26];
66        let mut vb = vec![0; 26];
67        for c in a.chars() {
68            va[c as usize - 'a' as usize] += 1;
69        }
70
71        for c in b.chars() {
72            vb[c as usize - 'a' as usize] += 1;
73        }
74
75        va == vb
76    }
77}
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_2273_1() {
87        assert_eq!(
88            Solution::remove_anagrams(vec![
89                "abba".to_string(),
90                "baba".to_string(),
91                "bbaa".to_string(),
92                "cd".to_string(),
93                "cd".to_string()
94            ]),
95            vec!["abba".to_string(), "cd".to_string()]
96        );
97
98        assert_eq!(
99            Solution::remove_anagrams(vec![
100                "a".to_string(),
101                "b".to_string(),
102                "c".to_string(),
103                "d".to_string(),
104                "e".to_string(),
105            ]),
106            vec![
107                "a".to_string(),
108                "b".to_string(),
109                "c".to_string(),
110                "d".to_string(),
111                "e".to_string(),
112            ]
113        );
114    }
115}
116