Skip to content

2273. Find Resultant Array After Removing Anagrams

  • Time: $O(\Sigma |\texttt{words[i]}|)$
  • Space: $O(\Sigma |\texttt{words[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  vector<string> removeAnagrams(vector<string>& words) {
    vector<string> ans;

    for (int i = 0; i < words.size();) {
      int j = i + 1;
      while (j < words.size() && isAnagram(words[i], words[j]))
        ++j;
      ans.push_back(words[i]);
      i = j;
    }

    return ans;
  }

 private:
  bool isAnagram(const string& a, const string& b) {
    if (a.length() != b.length())
      return false;

    vector<int> count(26);

    for (const char c : a)
      ++count[c - 'a'];

    for (const char c : b)
      --count[c - 'a'];

    return ranges::all_of(count, [](const int c) { return c == 0; });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public List<String> removeAnagrams(String[] words) {
    List<String> ans = new ArrayList<>();

    for (int i = 0; i < words.length;) {
      int j = i + 1;
      while (j < words.length && isAnagram(words[i], words[j]))
        ++j;
      ans.add(words[i]);
      i = j;
    }

    return ans;
  }

  private boolean isAnagram(final String a, final String b) {
    if (a.length() != b.length())
      return false;

    int[] count = new int[26];

    for (final char c : a.toCharArray())
      ++count[c - 'a'];

    for (final char c : b.toCharArray())
      --count[c - 'a'];

    return Arrays.stream(count).allMatch(c -> c == 0);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def removeAnagrams(self, words: list[str]) -> list[str]:
    ans = []

    def isAnagram(a: str, b: str) -> bool:
      count = collections.Counter(a)
      count.subtract(collections.Counter(b))
      return all(value == 0 for value in count.values())

    i = 0
    while i < len(words):
      j = i + 1
      while j < len(words) and isAnagram(words[i], words[j]):
        j += 1
      ans.append(words[i])
      i = j

    return ans