Find Resultant Array After Removing Anagrams

Easy

#2071Time: 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.1 company

Algorithms

Sorting

Data structures

Array Hash Table String

Companies

J.P. Morgan

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    private String getCanonical(String s) {7        char[] chars = s.toCharArray();8        Arrays.sort(chars);9        return new String(chars);10    }11 12    public List<String> removeAnagrams(String[] words) {13        List<String> result = new ArrayList<>();14        String lastCanonical = ""; // An initial value that won't match15        16        for (String word : words) {17            String currentCanonical = getCanonical(word);18            if (!currentCanonical.equals(lastCanonical)) {19                result.add(word);20                lastCanonical = currentCanonical;21            }22        }23        24        return result;25    }26}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    private int[] getFrequency(String s) {7        int[] counts = new int[26];8        for (char c : s.toCharArray()) {9            counts[c - 'a']++;10        }11        return counts;12    }13 14    public List<String> removeAnagrams(String[] words) {15        List<String> result = new ArrayList<>();16        int[] lastFrequency = new int[0]; // Initial state that won't match17        18        for (String word : words) {19            int[] currentFrequency = getFrequency(word);20            if (!Arrays.equals(currentFrequency, lastFrequency)) {21                result.add(word);22                lastFrequency = currentFrequency;23            }24        }25        26        return result;27    }28}

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  List<String> removeAnagrams(String[] words) {4    List<String> ans = new ArrayList<>();5    String prev = "";6    for (String w : words) {7      char[] cs = w.toCharArray();8      Arrays.sort(cs);9      String t = String.valueOf(cs);10      if (!t.equals(prev)) {11        ans.add(w);12      }13      prev = t;14    }15    return ans;16  }17}

1class Solution {2public:3  vector<string> removeAnagrams(vector<string> &words) {4    auto check = [](string &s, string &t) -> bool {5      if (s.size() != t.size()) {6        return true;7      }8      int cnt[26]{};9      for (char &c : s) {10        ++cnt[c - 'a'];11      }12      for (char &c : t) {13        if (--cnt[c - 'a'] < 0) {14          return true;15        }16      }17      return false;18    };19    vector<string> ans = {words[0]};20    for (int i = 1; i < words.size(); ++i) {21      if (check(words[i - 1], words[i])) {22        ans.emplace_back(words[i]);23      }24    }25    return ans;26  }27};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem