Problem of The Day: Find Resultant Array After Removing Anagrams

4 min read 875 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        res = []
        prev_anagram = ""
        for word in words:
            sorted_word = "".join(sorted(list(word)))
            if not res or prev_anagram != sorted_word:
                res.append(word)
            prev_anagram = sorted_word[:]

        return res

Time: O(n*mlogm) where n is the number of words and m is the length of the longest word Space: O(n*m)

public class Solution {
    public IList<string> RemoveAnagrams(string[] words) {
        List<string> result = new List<string>();
        var prevAnagram = new int[26];
        foreach (string word in words) {
            var currAnagram = new int[26];
            foreach (char ch in word) {
                int i = ch - 'a';
                currAnagram[i] += 1;
            }
            if (result.Count == 0) {
                result.Add(word);
            } else {
                bool isValid = false;
                for (int i = 0; i < 26; i++) {
                    if (currAnagram[i] != prevAnagram[i]) {
                        isValid = true;
                        break;
                    }
                }
                if (isValid) {
                    result.Add(word);
                }
            }

            prevAnagram = currAnagram.ToArray();
        }


        return result;
    }
}

Editorial

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        res = [words[0]]  # result array
        n = len(words)

        # determine if two words are anagrams
        def compare(word1: str, word2: str) -> bool:
            freq = [0] * 26
            for ch in word1:
                freq[ord(ch) - ord("a")] += 1
            for ch in word2:
                freq[ord(ch) - ord("a")] -= 1
            return all(x == 0 for x in freq)

        for i in range(1, n):
            if compare(words[i], words[i - 1]):
                continue
            res.append(words[i])
        return res

public class Solution {
    public IList<string> RemoveAnagrams(string[] words) {
        List<string> res = new List<string>();
        res.Add(words[0]);  // result array
        int n = words.Length;

        for (int i = 1; i < n; i++) {
            if (!Compare(words[i], words[i - 1])) {
                res.Add(words[i]);
            }
        }
        return res;
    }

    // determine if two words are anagrams
    private bool Compare(string word1, string word2) {
        int[] freq = new int[26];
        foreach (char ch in word1) {
            freq[ch - 'a']++;
        }
        foreach (char ch in word2) {
            freq[ch - 'a']--;
        }
        foreach (int x in freq) {
            if (x != 0) {
                return false;
            }
        }
        return true;
    }
}