# Find Resultant Array After Removing Anagrams
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-resultant-array-after-removing-anagrams)
Canonical: https://scaleengineer.com/dsa/problems/find-resultant-array-after-removing-anagrams
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
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.

# Approaches
## Single Pass with Cached Sorted String
This approach iterates through the input array `words` a single time. It determines whether to keep a word by comparing it to the last word that was kept. To simplify the anagram check, it converts each word into a "canonical form". For this approach, the canonical form is the string created by sorting the word's characters alphabetically. If the current word's canonical form is different from the last kept word's canonical form, the current word is added to the result.
**Time:** O(N * K log K), where `N` is the number of words and `K` is the maximum length of a word. We iterate through `N` words. For each word, we compute its canonical form by sorting its characters, which takes `O(K log K)` time. · **Space:** O(N * K), where `N` is the number of words and `K` is the maximum length of a word. This space is primarily used for the `result` list. Additionally, `O(K)` space is used temporarily for the character arrays and canonical strings within the loop.
**Pros:** The logic is straightforward and easy to implement using built-in sorting functions.; It solves the problem in a single pass, which is much more efficient than repeated deletions on a list.
**Cons:** The sorting step (`O(K log K)`) for each word makes this approach less efficient than using frequency counts, especially for longer words.
### Explanation
The core idea is that two words are anagrams if and only if their sorted character sequences are identical. For example, `"baba"` and `"abba"` both become `"aabb"` when sorted. We can leverage this property.

We process the `words` array from left to right. We keep a variable, `lastCanonical`, to store the sorted form of the last word we added to our result list. For each new word we encounter, we compute its sorted form, `currentCanonical`. If `currentCanonical` is the same as `lastCanonical`, we know it's an anagram of the previous word and we discard it. If it's different, we add the new word to our result list and update `lastCanonical` with `currentCanonical`.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private String getCanonical(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    public List<String> removeAnagrams(String[] words) {
        List<String> result = new ArrayList<>();
        String lastCanonical = ""; // An initial value that won't match
        
        for (String word : words) {
            String currentCanonical = getCanonical(word);
            if (!currentCanonical.equals(lastCanonical)) {
                result.add(word);
                lastCanonical = currentCanonical;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize an empty `ArrayList` called `result`.
- If the input `words` array is empty, return the empty list.
- Create a placeholder string `lastCanonical` initialized to an empty string or any value that won't match a real canonical string.
- Iterate through each `word` in the input `words` array.
- For each `word`, compute its "canonical form". A canonical form is a representation that is identical for all anagrams of a word. Here, we use the sorted version of the string as its canonical form.
- To get the canonical form, convert the `word` to a character array, sort the array, and convert it back to a string.
- Compare the `currentCanonical` form with the `lastCanonical` form.
- If they are not equal, it means the current `word` is not an anagram of the previously kept word. In this case, add the `word` to the `result` list and update `lastCanonical` to the `currentCanonical` form.
- If they are equal, do nothing, effectively skipping the current word.
- After iterating through all the words, return the `result` list.

## Single Pass with Cached Frequency Array
This approach is an optimization of the previous one. It also performs a single pass over the input array but uses a more efficient method for the anagram check. Instead of sorting strings, it calculates the character frequency count for each word (e.g., using an array of 26 integers for lowercase English letters). A word is kept if its frequency count differs from the last kept word's frequency count. This avoids the `O(K log K)` sorting overhead, leading to a better time complexity.
**Time:** O(N * K), where `N` is the number of words and `K` is the maximum length of a word. We iterate through `N` words. For each word, computing its frequency array takes `O(K)` time. Comparing two frequency arrays takes `O(1)` time as the alphabet size is constant. · **Space:** O(N * K), where `N` is the number of words and `K` is the maximum length of a word. This is for storing the `result` list. The space for the frequency arrays is `O(1)` because their size (26) is constant and does not depend on the input size.
**Pros:** Achieves the optimal time complexity for this problem.; More efficient than the sorting approach, especially as the length of words (`K`) increases.
**Cons:** The logic for creating and comparing frequency arrays is slightly more complex to write than simply sorting and comparing strings.
### Explanation
Two strings are anagrams if they have the exact same character counts. We can represent the character counts of a string using an integer array of size 26. For example, the word `"baba"` would be represented by an array where the count for 'a' is 2, the count for 'b' is 2, and all other counts are 0.

This method iterates through the words, calculating the frequency array for each. It compares the current word's frequency array with the frequency array of the last word added to the result. If the arrays are different, the word is kept. This is more efficient because calculating the frequency array takes linear time (`O(K)`) with respect to the word's length, which is better than the `O(K log K)` time required for sorting.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private int[] getFrequency(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        return counts;
    }

    public List<String> removeAnagrams(String[] words) {
        List<String> result = new ArrayList<>();
        int[] lastFrequency = new int[0]; // Initial state that won't match
        
        for (String word : words) {
            int[] currentFrequency = getFrequency(word);
            if (!Arrays.equals(currentFrequency, lastFrequency)) {
                result.add(word);
                lastFrequency = currentFrequency;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize an empty `ArrayList` called `result`.
- If the input `words` array is empty, return the empty list.
- Initialize a `lastFrequency` integer array of size 26 to a non-matching initial state (e.g., an empty array or an array of -1s).
- Iterate through each `word` in the input `words` array.
- For each `word`, compute its character frequency array. This is an integer array of size 26 where the i-th element stores the count of the i-th letter of the alphabet.
- Compare the `currentFrequency` array with the `lastFrequency` array using `Arrays.equals()`.
- If the arrays are not equal, it signifies that the current `word` is not an anagram of the previously kept word. Add the `word` to the `result` list and update `lastFrequency` to be the `currentFrequency` array.
- If the arrays are equal, do nothing.
- After the loop finishes, return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<String> removeAnagrams(String[] words) {
    List<String> ans = new ArrayList<>();
    String prev = "";
    for (String w : words) {
      char[] cs = w.toCharArray();
      Arrays.sort(cs);
      String t = String.valueOf(cs);
      if (!t.equals(prev)) {
        ans.add(w);
      }
      prev = t;
    }
    return ans;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]: return [
        w for i, w in enumerate(words) if i == 0 or sorted(w) != sorted(words[i - 1])]

```