algoadvance

Leetcode 2273. Find Resultant Array After Removing Anagrams

Problem Statement

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters. In one operation, you can remove any anagram of words[i] in words, if there is one. You need to return the resultant array after removing all anagrams.

An anagram of a word is a word that can be rearranged to form the same word. For instance, “baba” and “aabb” are anagrams of each other, however, “bbaa” and “abb” are not anagrams.

Example

Constraints

Clarifying Questions

  1. Should the order of words be preserved in the resultant array? Yes, the order should be preserved.
  2. Is it possible to have words in the input array that are not anagrams of any other word? Yes, it’s possible.
  3. Can the string array contain duplicates of the same word? Yes, it can.

Strategy

  1. Iterate over the list of words.
  2. For every word, sort the characters in the word and use this sorted version to keep track of its appearance.
  3. If a sorted version of the word has already been seen, skip adding it to the resultant list.
  4. Otherwise, add it to the resultant list and mark the sorted version as seen.

This approach will ensure every group of anagrams appears only once in the output list, with the first occurrence preserved.

Code

import java.util.*;

public class Solution {
    public List<String> removeAnagrams(String[] words) {
        List<String> result = new ArrayList<>();
        Set<String> seen = new HashSet<>();

        for (String word : words) {
            char[] charArray = word.toCharArray();
            Arrays.sort(charArray);
            String sortedWord = new String(charArray);
            
            if (!seen.contains(sortedWord)) {
                result.add(word);
                seen.add(sortedWord);
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"abba", "baba", "bbaa", "cd", "dc"};
        List<String> result = sol.removeAnagrams(words);
        System.out.println(result);  // Output: ["abba", "cd"]
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI