Collapse runs of adjacent anagrams in a word list

You are given a list of lowercase words. Two words are anagrams of each other when one can be turned into the other by rearranging its letters, using every letter exactly once. In particular, two identical words are anagrams, and two words of different lengths never are.

While there is an index i with 0 < i < len(words) such that words[i - 1] and words[i] are anagrams, delete words[i] from the list. Return the list that remains once no such index exists.

Function Signature

def remove_adjacent_anagrams(words: list[str]) -> list[str]:

Rules

• Only neighbors in the current list are compared. After a deletion, the word that moves into position i is compared with the word now before it.
• The remaining words keep their original relative order.
• The order in which eligible deletions are performed does not change the final list, so the answer is unique.
• Return a new list. The input list may be left unchanged.

Constraints

• 1 <= len(words) <= 100
• 1 <= len(words[i]) <= 10
• Every word consists only of lowercase English letters a to z.

Examples

Example 1

Input:  words = ["listen", "silent", "enlist", "google", "gogole", "cat", "act", "tac", "dog"]
Output: ["listen", "google", "cat", "dog"]

"silent" and "enlist" are anagrams of "listen" and are deleted. "gogole" uses the same letters as "google". "act" and "tac" are anagrams of "cat". "dog" is not an anagram of "tac".

Example 2

Input:  words = ["a", "b", "a", "a", "ab", "ba", "abc"]
Output: ["a", "b", "a", "ab", "abc"]

The first and third words are both "a", but they are not neighbors, so both stay. The fourth word is deleted because it equals its neighbor. "ba" is an anagram of "ab". "abc" has a different length from "ab".

Example 3

Input:  words = ["abc", "abcd", "dcba", "bcad"]
Output: ["abc", "abcd"]

"abcd" has a different length from "abc", so it stays. "dcba" is an anagram of "abcd" and is deleted; "bcad" then becomes the neighbor of "abcd", is also an anagram of it, and is deleted too.

Delete Words That Are Anagrams of Their Left Neighbor

Hints

1. By the definition, identical words are anagrams and words of different lengths never are. Make sure your anagram test agrees with both facts.
2. Using the same letters is not enough: every letter must be used exactly once, so 'aab' and 'abb' are not anagrams even though both contain only a and b.
3. Trace Example 2 by hand: after 'dcba' is deleted, note which word 'bcad' is compared with, and ask whether the first word of the list can ever be deleted.

Approach

Two words are anagrams exactly when their letters, sorted alphabetically, form the same string. That sorted key automatically separates words of different lengths, and words like 'aab' and 'abb' that share a letter set but not letter counts. Being anagrams is therefore an equivalence relation. Scan the words left to right, building the result and remembering the key of the last word kept. The first word is always kept because it never has a left neighbor. When a later word is examined, every word between it and the last kept word has already been deleted, so its left neighbor in the current list is exactly the last kept word. If the two keys are equal, the word is deleted (skipped). Otherwise it is appended and its key becomes the new comparison key. Invariant: after processing words[0..k], the result is the fully reduced list for that prefix, and no two adjacent words in it are anagrams. A later word can only cause its own deletion, never that of an earlier kept word, so the reduced prefix never changes again. Because the relation is transitive, each maximal run of consecutive words from one anagram class collapses to its first word, which is why the order of deletions does not matter. Edge cases: a single word is returned unchanged; equal words that are not neighbors both stay; a word of a different length always stays; after a run of one class ends, comparison restarts with the first word of the new run. The input list is not modified.

• Time complexity: O(n * L log L), where n = len(words) and L <= 10 is the maximum word length
• Space complexity: O(n) for the returned list, plus O(L) for one sorted key