Problem Description

You have an array of strings called words where each string contains only lowercase English letters. Your task is to remove consecutive anagram pairs from this array.

The removal process works as follows:

• Look for any position i (where 0 < i < words.length) where words[i-1] and words[i] are anagrams of each other
• When you find such a pair, delete words[i] from the array
• Continue this process until no more consecutive anagram pairs exist

Two strings are anagrams if one can be formed by rearranging the letters of the other, using all letters exactly once. For example, "dacb" and "abdc" are anagrams because they contain the same letters in different orders.

The key insight is that you only remove the second word in each anagram pair (at index i), keeping the first word (at index i-1). This means if you have multiple consecutive anagrams like ["abc", "bca", "cab"], you would remove "bca" first (since it's an anagram of "abc"), then check again and remove "cab" (since it's now consecutive with "abc").

The problem guarantees that regardless of the order in which you perform the removals, you'll always end up with the same final result. Your goal is to return the array after all possible removals have been made.

For example:

• Input: ["abba", "baba", "bbaa", "cd", "cd"]
• After removing "baba" (anagram of "abba"): ["abba", "bbaa", "cd", "cd"]
• After removing "bbaa" (anagram of "abba"): ["abba", "cd", "cd"]
• After removing the second "cd" (anagram of first "cd"): ["abba", "cd"]
• Output: ["abba", "cd"]

Intuition

The key observation is that we need to keep removing consecutive anagram pairs until no more can be removed. At first glance, this might seem like we need to repeatedly scan the array and remove elements, which could be inefficient.

However, let's think about what happens during the removal process. When we remove words[i] because it's an anagram of words[i-1], the element at words[i+1] now becomes adjacent to words[i-1]. But here's the crucial insight: if words[i+1] were an anagram of words[i-1], we would need to remove it too. This process continues until we find a word that is NOT an anagram of words[i-1].

This means that for any position in the original array, we only keep a word if it's not an anagram of the word we kept immediately before it. In other words, we can solve this problem in a single pass through the array by maintaining only the words that are not anagrams of their immediate predecessor in our result.

The algorithm becomes straightforward:

1. Always keep the first word (it has no predecessor to compare with)
2. For each subsequent word, check if it's an anagram of the last word we kept
3. If it's not an anagram, keep it; otherwise, skip it

This works because removing a word doesn't affect whether future words are anagrams of previously kept words - it only matters whether each word is an anagram of the most recently kept word.

To check if two strings are anagrams, we can either:

• Sort both strings and compare them
• Count the frequency of each character and compare the counts

The solution uses the second approach with a Counter to track character frequencies, checking if the counts match between the two strings.

Learn more about Sorting patterns.

Solution Approach

The solution implements a single-pass approach using a helper function to check if two strings are anagrams.

Helper Function check(s, t):

This function determines if two strings are NOT anagrams (returns True if they're different, False if they're anagrams):

1. First, compare the lengths of s and t. If they differ, they cannot be anagrams, so return True.

2. Use a Counter to count the frequency of each character in string s.

3. Iterate through each character c in string t:

   • Decrement the count for character c by 1: cnt[c] -= 1
   • If cnt[c] < 0, it means t has more occurrences of character c than s, so they're not anagrams - return True

4. If we successfully process all characters in t without any count going negative, the strings are anagrams - return False.

Main Solution:

The main solution uses Python's pairwise function to elegantly handle consecutive pair comparisons:

return [words[0]] + [t for s, t in pairwise(words) if check(s, t)]

This works as follows:

1. Start with words[0] in the result (the first word is always kept since it has no predecessor).

2. Use pairwise(words) to generate all consecutive pairs (words[i], words[i+1]) from the array.

3. For each pair (s, t) where s = words[i] and t = words[i+1]:

   • If check(s, t) returns True (meaning they're NOT anagrams), include t in the result
   • If check(s, t) returns False (meaning they ARE anagrams), skip t

This approach effectively filters out any word that is an anagram of its immediate predecessor, achieving the desired result in a single pass with O(n * m) time complexity, where n is the number of words and m is the average length of each word.

The beauty of this solution is that it recognizes we don't need to actually perform removals - we can directly construct the final result by keeping only the words that wouldn't be removed.

Example Walkthrough

Let's walk through a small example: words = ["abc", "bca", "xyz", "zyx", "z"]

Step 1: Initialize result with first word

• Result starts with ["abc"] (first word is always kept)

Step 2: Process consecutive pairs using the check function

For pair ("abc", "bca"):

• Check if they're anagrams:
  • Both have length 3 ✓
  • Count characters in "abc": {'a':1, 'b':1, 'c':1}
  • Process "bca":
    • 'b': count becomes {'a':1, 'b':0, 'c':1}
    • 'c': count becomes {'a':1, 'b':0, 'c':0}
    • 'a': count becomes {'a':0, 'b':0, 'c':0}
  • No negative counts, so they ARE anagrams
• check("abc", "bca") returns False → skip "bca"
• Result: ["abc"]

For pair ("bca", "xyz"):

• Even though we skipped "bca", pairwise still generates this pair from the original array
• Check if they're anagrams:
  • Both have length 3 ✓
  • Count characters in "bca": {'b':1, 'c':1, 'a':1}
  • Process "xyz":
    • 'x': not in counter, so count becomes -1
  • Count went negative, so they're NOT anagrams
• check("bca", "xyz") returns True → include "xyz"
• Result: ["abc", "xyz"]

For pair ("xyz", "zyx"):

• Check if they're anagrams:
  • Both have length 3 ✓
  • Count characters in "xyz": {'x':1, 'y':1, 'z':1}
  • Process "zyx":
    • 'z': count becomes {'x':1, 'y':1, 'z':0}
    • 'y': count becomes {'x':1, 'y':0, 'z':0}
    • 'x': count becomes {'x':0, 'y':0, 'z':0}
  • No negative counts, so they ARE anagrams
• check("xyz", "zyx") returns False → skip "zyx"
• Result: ["abc", "xyz"]

For pair ("zyx", "z"):

• Check if they're anagrams:
  • Different lengths (3 vs 1)
• check("zyx", "z") returns True → include "z"
• Result: ["abc", "xyz", "z"]

Final Result: ["abc", "xyz", "z"]

The solution correctly identified and skipped the anagram pairs ("abc"/"bca" and "xyz"/"zyx"), keeping only the non-consecutive anagram words.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m), where n is the number of words in the array and m is the average length of each word. This is because:

• We iterate through all pairs of consecutive words using pairwise(words), which takes O(n) iterations
• For each pair, the check function is called, which:
  • Compares lengths in O(1)
  • Creates a Counter from string s in O(m) time
  • Iterates through string t to decrement counts in O(m) time
• Therefore, the total time is O(n × m)

Since the total length of all words combined is L, and L = n × m, the time complexity can also be expressed as O(L).

The space complexity is O(|Σ|) where |Σ| = 26 for lowercase English letters. This is because:

• The Counter object in the check function stores at most |Σ| unique characters
• The output list in the worst case contains all n words, but this is considered part of the output and not auxiliary space
• The pairwise iterator and other variables use O(1) additional space

Therefore, the auxiliary space complexity is O(26) = O(1) or more precisely O(|Σ|).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Removal Process

The Mistake: Many developers initially think they need to repeatedly scan the entire array after each removal, implementing something like:

def removeAnagrams(self, words: List[str]) -> List[str]:
    changed = True
    while changed:
        changed = False
        i = 1
        while i < len(words):
            if are_anagrams(words[i-1], words[i]):
                words.pop(i)
                changed = True
            else:
                i += 1
    return words

Why It's Wrong: This approach has several issues:

1. Inefficiency: It has O(n²) iterations in the worst case
2. Unnecessary complexity: The problem guarantees a unique final result regardless of removal order
3. Modifying the list while iterating can lead to bugs

The Fix: Recognize that you only need a single pass. Once you decide whether to keep a word based on its predecessor, that decision is final:

result = [words[0]]
for i in range(1, len(words)):
    if not are_anagrams(words[i-1], words[i]):
        result.append(words[i])
return result

Pitfall 2: Comparing Against the Wrong Previous Word

The Mistake: Some solutions incorrectly compare each word against the last word added to the result:

def removeAnagrams(self, words: List[str]) -> List[str]:
    result = [words[0]]
    for i in range(1, len(words)):
        # WRONG: Comparing with result[-1] instead of words[i-1]
        if not are_anagrams(result[-1], words[i]):
            result.append(words[i])
    return result

Why It's Wrong: This changes the problem's semantics. Consider ["abc", "xyz", "bca"]:

• Correct approach: Compare "xyz" with "abc" (not anagrams, keep "xyz"), then "bca" with "xyz" (not anagrams, keep "bca"). Result: ["abc", "xyz", "bca"]
• Wrong approach: Compare "bca" with "abc" (ARE anagrams, skip "bca"). Result: ["abc", "xyz"]

The Fix: Always compare consecutive words from the original array:

for prev_word, curr_word in pairwise(words):
    if is_not_anagram(prev_word, curr_word):
        result.append(curr_word)

Pitfall 3: Incorrect Anagram Checking

The Mistake: Using set comparison or simple character counting without considering frequency:

def are_anagrams(s, t):
    # WRONG: This only checks if they have the same unique characters
    return set(s) == set(t)

# Or
def are_anagrams(s, t):
    # WRONG: This doesn't account for character frequency
    return all(c in t for c in s) and all(c in s for c in t)

Why It's Wrong:

• set("aab") == set("ab") returns True, but "aab" and "ab" are not anagrams
• The second approach would consider "aaa" and "a" as anagrams

The Fix: Use proper frequency counting:

def are_anagrams(s, t):
    return Counter(s) == Counter(t)
# Or use sorted comparison
def are_anagrams(s, t):
    return sorted(s) == sorted(t)

Pitfall 4: Edge Case Handling

The Mistake: Not handling single-element arrays or assuming the array has at least 2 elements:

def removeAnagrams(self, words: List[str]) -> List[str]:
    # WRONG: Assumes words has at least 2 elements
    result = [words[0]]
    for s, t in pairwise(words):  # This fails if len(words) == 1
        # ...

Why It's Wrong: When words = ["abc"], pairwise returns an empty iterator, but the code still works correctly because we initialize with words[0]. However, if you forget to initialize or handle empty arrays, it breaks.

The Fix: The provided solution handles this correctly by always including words[0] first. For extra safety, you could add:

if len(words) <= 1:
    return words
# Continue with main logic