Collapse runs of adjacent anagrams in a word list
Company: DocuSign
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given a list of lowercase words, repeatedly delete any word that is an anagram of the word immediately before it, and return what remains in its original order. The task tests anagram comparison, reasoning about how repeated deletions interact, and producing a unique, order-preserving result.
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.
Implement `remove_adjacent_anagrams(words)`, which returns the remaining list of words.
**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`.
**Example 1**
```text
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**
```text
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.
Constraints
- 1 <= len(words) <= 100
- 1 <= len(words[i]) <= 10
- Every word consists only of lowercase English letters 'a' to 'z'.
Examples
Input: (['a'],)
Expected Output: ['a']
Explanation: Minimum valid input: one one-letter word has no left neighbor, so it stays.
Input: (['z', 'z'],)
Expected Output: ['z']
Explanation: Smallest deletion: identical words are anagrams, so the second 'z' is deleted while the first word is never deleted.
Hints
- By the definition, identical words are anagrams and words of different lengths never are. Make sure your anagram test agrees with both facts.
- 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.
- 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.