We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Resultant Array After Removing Anagrams

Number: 1353

Difficulty: Easy

Paid? No

Companies: Bloomberg, J.P. Morgan, NextJump

Problem Description

Given an array of strings, remove every word that is an anagram of the previous word (i.e. any adjacent pair that are anagrams). Continue performing this operation until no such adjacent anagram exists, and return the resulting array.

Key Insights

  • Two words are anagrams if their sorted characters are identical.
  • Only adjacent words need to be compared.
  • The order of operations does not affect the final result.
  • A single-pass solution using a stack (or result list) is sufficient.

Space and Time Complexity

Time Complexity: O(n * m log m), where n is the number of words and m is the maximum length of a word (due to sorting each word).
Space Complexity: O(n * m), for storing the result list and the sorted character arrays.

Solution

We use a greedy one-pass approach with a result list (or stack).

  1. Initialize the result with the first word of the input array.
  2. Iterate through the remaining words. For each word, compare its sorted character sequence with that of the last word in the result list.
  3. If they are not equal (i.e. not anagrams), add the word to the result list.
  4. Return the final result list.

This works because removing a word when it is an anagram of its predecessor leads to the same final set irrespective of the order of removals.

Code Solutions

def remove_anagrams(words):
    # Initialize the result list with the first word
    result = [words[0]]
    
    # Iterate from the second word to the end
    for word in words[1:]:
        # Check if the current word is an anagram of the last word in result by comparing sorted characters
        if sorted(word) != sorted(result[-1]):
            result.append(word)  # If not an anagram, add it to the result list
    return result

# Example usage:
words = ["abba", "baba", "bbaa", "cd", "cd"]
print(remove_anagrams(words))  # Output: ['abba', 'cd']
← Back to All Questions