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.