Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Anagrams have identical character frequencies. Consecutive words with the same frequency signature form a run, and repeated allowed deletions leave only its first word. Different neighboring signatures stay different, so no additional cross-run merging is needed.

Approach

Precompute a character-frequency map for every word. Keep the first word, then retain each later word only when its map differs from the immediately previous original word's map. This marks precisely the starts of signature runs, equivalent to repeatedly deleting an anagram of the previous retained word. Return the retained words in their original order. Duplicate spellings are handled as anagrams too.

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        n = len(words)
        # precompute fm for every word
        c = {}

        for i in range(n):
            c[i] = Counter(words[i])

        # iterate, compare, and get result
        res = [words[0]]
        for i in range(1, n):
            if c[i] != c[i - 1]:
                res.append(words[i])

        return res

Complexity analysis

Let C be the total number of characters across all words. Both displayed implementations precompute a frequency map for each word and compare adjacent maps, taking O(C) time and O(C) auxiliary counter space, excluding the returned array.