LeetCode 2273. Find Resultant Array After Removing Anagrams Solution in Java, C++, Python & More | Explanation + Code

Description

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

 

Example 1:

Input: words = ["abba","baba","bbaa","cd","cd"]
Output: ["abba","cd"]
Explanation:
One of the ways we can obtain the resultant array is by using the following operations:
- Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","baba","cd","cd"].
- Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1].
  Now words = ["abba","cd","cd"].
- Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","cd"].
We can no longer perform any operations, so ["abba","cd"] is the final answer.

Example 2:

Input: words = ["a","b","c","d","e"]
Output: ["a","b","c","d","e"]
Explanation:
No two adjacent strings in words are anagrams of each other, so no operations are performed.

 

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.

Solutions

Solution 1: Simulation

We first add words[0] to the answer array, then traverse from words[1]. If words[i - 1] and words[i] are not anagrams, we add words[i] to the answer array.

The problem is converted to determining whether two strings are anagrams. We define a helper function check(s, t) to achieve this. If s and t are not anagrams, we return true; otherwise, we return false.

In the function check(s, t), we first check if the lengths of s and t are equal. If they are not, we return true. Otherwise, we use an array cnt of length 26 to count the occurrences of each character in s, then traverse each character in t and decrement cnt[c] by 1. If cnt[c] is less than 0, we return true. If we traverse all characters in t without issues, it means s and t are anagrams, and we return false.

The time complexity is O(L), and the space complexity is O(|Σ|). Here, L is the length of the array words, and Σ is the character set, which is lowercase English letters, so |Σ| = 26.

PythonJavaC++GoTypeScriptRustJavaScript

class Solution: def removeAnagrams(self, words: List[str]) -> List[str]: def check(s: str, t: str) -> bool: if len(s) != len(t): return True cnt = Counter(s) for c in t: cnt[c] -= 1 if cnt[c] < 0: return True return False return [words[0]] + [t for s, t in pairwise(words) if check(s, t)](code-box)

class Solution { public List<String> removeAnagrams(String[] words) { List<String> ans = new ArrayList<>(); ans.add(words[0]); for (int i = 1; i < words.length; ++i) { if (check(words[i - 1], words[i])) { ans.add(words[i]); } } return ans; } private boolean check(String s, String t) { if (s.length() != t.length()) { return true; } int[] cnt = new int[26]; for (int i = 0; i < s.length(); ++i) { ++cnt[s.charAt(i) - 'a']; } for (int i = 0; i < t.length(); ++i) { if (--cnt[t.charAt(i) - 'a'] < 0) { return true; } } return false; } }(code-box)

class Solution { public: vector<string> removeAnagrams(vector<string>& words) { auto check = [](string& s, string& t) -> bool { if (s.size() != t.size()) { return true; } int cnt[26]{}; for (char& c : s) { ++cnt[c - 'a']; } for (char& c : t) { if (--cnt[c - 'a'] < 0) { return true; } } return false; }; vector<string> ans = {words[0]}; for (int i = 1; i < words.size(); ++i) { if (check(words[i - 1], words[i])) { ans.emplace_back(words[i]); } } return ans; } };(code-box)

func removeAnagrams(words []string) []string { ans := []string{words[0]} check := func(s, t string) bool { if len(s) != len(t) { return true } cnt := [26]int{} for _, c := range s { cnt[c-'a']++ } for _, c := range t { cnt[c-'a']-- if cnt[c-'a'] < 0 { return true } } return false } for i, t := range words[1:] { if check(words[i], t) { ans = append(ans, t) } } return ans }(code-box)

function removeAnagrams(words: string[]): string[] { const ans: string[] = [words[0]]; const check = (s: string, t: string): boolean => { if (s.length !== t.length) { return true; } const cnt: number[] = Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt(0) - 97]; } for (const c of t) { if (--cnt[c.charCodeAt(0) - 97] < 0) { return true; } } return false; }; for (let i = 1; i < words.length; ++i) { if (check(words[i - 1], words[i])) { ans.push(words[i]); } } return ans; }(code-box)

impl Solution { pub fn remove_anagrams(words: Vec<String>) -> Vec<String> { fn check(s: &str, t: &str) -> bool { if s.len() != t.len() { return true; } let mut cnt = [0; 26]; for c in s.bytes() { cnt[(c - b'a') as usize] += 1; } for c in t.bytes() { let idx = (c - b'a') as usize; cnt[idx] -= 1; if cnt[idx] < 0 { return true; } } false } let mut ans = vec![words[0].clone()]; for i in 1..words.len() { if check(&words[i - 1], &words[i]) { ans.push(words[i].clone()); } } ans } }(code-box)

/** * @param {string[]} words * @return {string[]} */ var removeAnagrams = function (words) { const ans = [words[0]]; const check = (s, t) => { if (s.length !== t.length) { return true; } const cnt = Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt() - 97]; } for (const c of t) { if (--cnt[c.charCodeAt() - 97] < 0) { return true; } } return false; }; for (let i = 1; i < words.length; ++i) { if (check(words[i - 1], words[i])) { ans.push(words[i]); } } return ans; };(code-box)