Find Resultant Array After Removing Anagrams — LeetCode 2273 Python Solution

The problem

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters. In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words.

Example

Input

words = ["abba","baba","bbaa","cd","cd"]

Output

["abba","cd"]

Explanation

One of the ways we can obtain the resultant array is by using the following operations:

Python solution

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        def check(s: str, t: str) -> bool:
            if len(s) != len(t):
                return True
            cnt = Counter(s)
            for c in t:
                cnt[c] -= 1
                if cnt[c] < 0:
                    return True
            return False

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

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2273. Find Resultant Array After Removing Anagrams is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems