Find Resultant Array After Removing Anagrams

Easy
1197.

Find Resultant Array After Removing Anagrams

Find Resultant Array After Removing Anagrams is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

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 <= 100
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {string[]}
 */
var removeAnagrams = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters

Hints for Find Resultant Array After Removing Anagrams

  1. Hint 1

    Being anagrams is an equivalence: sort a word's letters to get a canonical key.

  2. Hint 2

    A word survives exactly when it is not an anagram of the word just before it in the original array.

  3. 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

  1. For each word compute key = sorted letters.
  2. Keep words[0].
  3. For i >= 1, keep words[i] when key(words[i]) != key(words[i-1]).
  4. 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 res

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings