EasyNo. 2273
Find Resultant Array After Removing Anagrams — LeetCode 2273 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, String, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
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
- Time
- O(L)
- Space · auxiliary
- O(|Σ|)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0049 | Group Anagrams | Medium |
| 0522 | Longest Uncommon Subsequence II | Medium |
| 0692 | Top K Frequent Words | Medium |
| 0720 | Longest Word in Dictionary | Medium |
| 0721 | Accounts Merge | Medium |
| 0792 | Number of Matching Subsequences | Medium |
Frequently asked questions
- How hard is LeetCode 2273. Find Resultant Array After Removing Anagrams?
LeetCode 2273. Find Resultant Array After Removing Anagrams is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2273. Find Resultant Array After Removing Anagrams?
The Python solution on this page runs in O(L).
- What is the space complexity of LeetCode 2273. Find Resultant Array After Removing Anagrams?
The Python solution on this page uses O(|Σ|) auxiliary space.
- What topics does LeetCode 2273. Find Resultant Array After Removing Anagrams cover?
LeetCode 2273. Find Resultant Array After Removing Anagrams is tagged Array, Hash Table, String and Sorting on LeetCode.