Find Resultant Array After Removing Anagrams

Difficulty: Easy | Acceptance: 69.90% | Paid: No Topics: Array, Hash Table, String, Sorting

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 not affect the final result.

An anagram is a string that contains the same characters in a different order.

• Examples
• Constraints
• Approach 1: Iterative Comparison with Sorting
• Approach 2: Iterative Comparison with Frequency Counting

Examples

Input: words = ["abba","baba","bbaa","cd","cd"]
Output: ["abba","cd"]
Explanation: 
One operation is performed on "baba" and "bbaa" because they are anagrams. The resulting array is ["abba","cd","cd"].
Another operation is performed on "cd" and "cd" because they are anagrams. The resulting array is ["abba","cd"].

Input: words = ["a","b","c","d","e"]
Output: ["a","b","c","d","e"]
Explanation: No two consecutive strings 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.

Approach 1: Iterative Comparison with Sorting

Intuition Two strings are anagrams if they contain the exact same characters. The simplest way to verify this is to sort the characters of both strings and check if the sorted results are identical. We iterate through the input list, comparing each word with the last word in our result list.

Steps

• Initialize an empty list result to store the final words.
• Iterate through each word in the input words array.
• If result is empty, add the current word to result.
• Otherwise, sort the characters of the current word and the last word in result.
• If the sorted strings are equal, the current word is an anagram of the previous one, so we skip it.
• If they are not equal, append the current word to result.
• Return result.

class Solution:
    def removeAnagrams(self, words: list[str]) -> list[str]:
        res = []
        for w in words:
            if not res:
                res.append(w)
            else:
                if sorted(w) == sorted(res[-1]):
                    continue
                res.append(w)
        return res

Complexity

• Time: O(N * K log K), where N is the number of words and K is the maximum length of a word. This is due to sorting each string.
• Space: O(N) to store the result list. Sorting takes O(K) space in Python/Java, but O(1) or O(log K) in C++/JS depending on implementation.
• Notes: Sorting is the most straightforward method but can be slightly slower than frequency counting for very long strings.

Approach 2: Iterative Comparison with Frequency Counting

Intuition Instead of sorting, we can count the frequency of each character in the strings. Two strings are anagrams if their character frequency counts are identical. This approach runs in linear time relative to the string length.

Steps

• Initialize an empty list result.
• Iterate through each word in words.
• If result is empty, add the current word.
• Otherwise, compare the character counts of the current word and the last word in result.
• If the counts match, skip the current word.
• If they differ, add the current word to result.
• Return result.

from collections import Counter

class Solution:
    def removeAnagrams(self, words: list[str]) -> list[str]:
        res = []
        for w in words:
            if not res:
                res.append(w)
            else:
                if Counter(w) == Counter(res[-1]):
                    continue
                res.append(w)
        return res

Complexity

• Time: O(N * K), where N is the number of words and K is the maximum length of a word. We iterate through each character once.
• Space: O(1) auxiliary space (since the alphabet size is fixed at 26), plus O(N) for the result list.
• Notes: This is theoretically more efficient than sorting for large strings, though for the given constraints (K <= 10), the difference is negligible.