Find Resultant Array After Removing Anagrams — Solution
Find Resultant Array After Removing Anagrams solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find Resultant Array After Removing Anagrams is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array words of lowercase strings. In one operation, pick an index i with 0 < i < words.length such that words[i - 1] and words[i] are anagrams (one is a rearrangement of the other's letters), and delete words[i].
Keep performing operations while any such index exists. Return the final array. The result is the same whatever order the operations are performed in.
Example 1
Input: words = ["kairo","oriak","duel","lude","duel","bug"]
Output: ["kairo","duel","bug"]
Explanation: `oriak` follows its anagram `kairo`; `lude` and the second `duel` follow anagrams of themselves.
Example 2
Input: words = ["a","b","c"]
Output: ["a","b","c"]
Example 3
Input: words = ["ab","ba","ab","ba"]
Output: ["ab"]
Constraints
1 <= words.length <= 1001 <= words[i].length <= 10words[i] consists of lowercase English letters
Hints for Find Resultant Array After Removing Anagrams
Hint 1
Being anagrams is an equivalence: sort a word's letters to get a canonical key.
Hint 2
A word survives exactly when it is not an anagram of the word just before it in the original array.
Hint 3
Walk the array once, keep a word if its key differs from the previous word's key, and always move the 'previous' key forward.
How to solve Find Resultant Array After Removing Anagrams
Deletions only ever remove a word that is an anagram of its left neighbour, so each maximal run of consecutive mutual anagrams collapses to its first word — and that is decided by comparing each word with the one right before it.
Approach
- For each word compute
key = sorted letters. - Keep
words[0]. - For
i >= 1, keepwords[i]whenkey(words[i]) != key(words[i-1]). - Return the kept words in order.
Why it works
Anagram-ness is transitive, so the array splits into maximal blocks of consecutive words sharing a key. Inside a block every word after the first has an anagram on its left and is eventually deleted, while the first word of a block never has an anagram immediately to its left (the word before it, or whatever block-first word ends up there, has a different key). Comparing each word with its original predecessor detects exactly the block starts.
Complexity
- Time —
O(n · L log L) - Space —
O(n · L)
Pitfalls
- Compare with the immediately preceding word, not with every earlier word —
["ab","c","ba"]keeps all three. - Equal words are anagrams of each other too.
- Sorting the letters (or counting them) is the anagram test; comparing lengths alone is not enough.
Reference solution
Python
from typing import List
def removeAnagrams(words: List[str]) -> List[str]:
res = []
prev = None
for w in words:
key = ''.join(sorted(w))
if key != prev:
res.append(w)
prev = key
return resJava
public static String[] removeAnagrams(String[] words) {
List<String> res = new ArrayList<>();
String prev = null;
for (String w : words) {
char[] a = w.toCharArray();
Arrays.sort(a);
String key = new String(a);
if (!key.equals(prev)) res.add(w);
prev = key;
}
return res.toArray(new String[0]);
}C++
vector<string> removeAnagrams(vector<string>& words) {
vector<string> res;
string prev;
for (int i = 0; i < (int)words.size(); i++) {
string key = words[i];
sort(key.begin(), key.end());
if (i == 0 || key != prev) res.push_back(words[i]);
prev = key;
}
return res;
}JavaScript
var removeAnagrams = function(words) {
var res = [];
var prev = null;
for (var i = 0; i < words.length; i++) {
var key = words[i].split("").sort().join("");
if (key !== prev) res.push(words[i]);
prev = key;
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.