Find Resultant Array After Removing Anagrams

main.md

Question

Approach

I scan the list and keep a result stack. For each word, I compare its sorted characters to the sorted characters of the last word kept. If they are anagrams (sorted equal), I skip the current word (simulate deleting it). Otherwise I append it to the stack. At the end the stack is the final array after all deletions. This works because deletions only depend on the most recent kept word and the process is order-independent.

Implementation

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        res = []
        for w in words:
            if res and sorted(res[-1]) == sorted(w):
                continue
            res.append(w)
        return res

Complexities

• Time: O(n⋅LlogL), where 𝑛 is number of words and L is max word length (sorting each word).
• Space: O(n⋅L) for the output and temporary sorted lists.