Here is two solution for problem “Find Resultant Array After Removing Anagrams”

1. Problem Definition

1. Input

• A list of lowercase words: words = [“abba”, “baba”, “bbaa”, “cd”, “cd”]

1. Output

• Remove adjacent words that are anagrams of each other.

• Return the remaining words in their original order.

• Example:

Input: [“abba”,”baba”,”bbaa”,”cd”,”cd”]

Output: [“abba”,”cd”]

• Explanation:

• “abba”, “baba”, and “bbaa” are all anagrams → keep only the first “abba”.

• “cd”, “cd” are identical → also anagrams → keep one “cd”.

1. Constraints

• 1 ≤ len(words) ≤ 1000

• Each word length ≤ 10

• All lowercase letters

2. Intuition / Idea

• Two words are anagrams if their sorted characters are equal:

“abba” → “aabb” “baba” → “aabb” “bbaa” → “aabb”

So the logic:

• Keep first word.

• For each next word, check if its sorted version == sorted(prev word).

  • If yes → skip it (they’re anagrams).
  • If not → keep it.

3. Dry Run Example

• Input:

[“abba”, “baba”, “bbaa”, “cd”, “cd”]

Step word sorted(word) prev_sorted Action Result 1 “abba” “aabb” — add [“abba”] 2 “baba” “aabb” “aabb” skip (anagram) [“abba”] 3 “bbaa” “aabb” “aabb” skip (anagram) [“abba”] 4 “cd” “cd” “aabb” add [“abba”,”cd”] 5 “cd” “cd” “cd” skip [“abba”,”cd”]

• ✅ Output: [“abba”, “cd”]

4. Implementation (O(N * L log L))

def removeAnagrams(words):
    res = [words[0]]
    for i in range(1, len(words)):
        if sorted(words[i]) != sorted(words[i - 1]):
            res.append(words[i])
    return res


# ✅ Test
print(removeAnagrams(["abba","baba","bbaa","cd","cd"]))
# Output: ["abba","cd"]

5. Complexity

• Sorting each word O(L log L)
• N words total O(N * L log L)
• Space O(N * L) (for output + sort buffer)

6. Optimization (O(N * L))

• Instead of sorting, we can count character frequencies (26 letters).
• Two words are anagrams if their counts match.

def removeAnagrams_fast(words):
    def encode(word):
        freq = [0] * 26
        for ch in word:
            freq[ord(ch) - ord('a')] += 1
        return tuple(freq)

    res = [words[0]]
    prev = encode(words[0])

    for i in range(1, len(words)):
        cur = encode(words[i])
        if cur != prev:
            res.append(words[i])
            prev = cur

    return res


# ✅ Test
print(removeAnagrams_fast(["abba","baba","bbaa","cd","cd"]))
# Output: ["abba","cd"]

✅ Now it’s linear in characters: O(N × L)

7. Summary

Approach	Idea	Time	Space
Sort-based	Compare sorted(word)	O(N × L log L)	O(N × L)
Count-based	Compare letter frequency tuple	O(N × L)	O(26 × N)

8. Enhance for case [“abba”,”baba”,”bbaa”,”cd”,”cd”,”baba”]

def removeAllAnagrams(words):
    seen = set()
    res = []

    for w in words:
        key = tuple(sorted(w))  # or use letter counts
        if key not in seen:
            res.append(w)
            seen.add(key)
    return res

print(removeAllAnagrams(["abba","baba","bbaa","cd","cd","baba"]))
# Output: ["abba", "cd"]

def removeAllAnagrams_optimized(words):
    def encode(word):
        # 26-length frequency vector
        freq = [0] * 26
        for ch in word:
            freq[ord(ch) - ord('a')] += 1
        return tuple(freq)  # hashable for set

    seen = set()
    res = []

    for w in words:
        key = encode(w)
        if key not in seen:
            seen.add(key)
            res.append(w)

    return res