Find Resultant Array After Removing Anagrams

easy array hash table string sorting

Problem

You are given a string array words. In one operation you may pick an index i (with 0 < i < words.length) where words[i−1] and words[i] are anagrams, and delete words[i]. Repeat while any such index exists, then return the remaining words. Two strings are anagrams when they use exactly the same letters with the same counts. The result is the same regardless of the order operations are applied.

Inputwords = ["abba","baba","bbaa","cd","cd"]

Output["abba","cd"]

"abba", "baba", "bbaa" are all anagrams, so only the first survives; the two "cd"s collapse to one.

words (comma-separated, lowercase letters)

def removeAnagrams(words):
    result = []                       # words that survive
    for w in words:
        sig = "".join(sorted(w))      # signature = letters sorted
        # drop w if it is an anagram of the last kept word
        if result and "".join(sorted(result[-1])) == sig:
            continue
        result.append(w)              # keep this word
    return result

function removeAnagrams(words) {
  const sig = (w) => w.split("").sort().join(""); // sorted letters
  const result = [];                  // words that survive
  for (const w of words) {
    // drop w if it is an anagram of the last kept word
    if (result.length && sig(result[result.length - 1]) === sig(w)) {
      continue;
    }
    result.push(w);                   // keep this word
  }
  return result;
}

List<String> removeAnagrams(String[] words) {
    List<String> result = new ArrayList<>();   // survivors
    for (String w : words) {
        // drop w if it is an anagram of the last kept word
        if (!result.isEmpty() &&
            sig(result.get(result.size() - 1)).equals(sig(w))) {
            continue;
        }
        result.add(w);                          // keep this word
    }
    return result;
}

String sig(String w) {                          // sorted letters
    char[] c = w.toCharArray();
    Arrays.sort(c);
    return new String(c);
}

vector<string> removeAnagrams(vector<string>& words) {
    auto sig = [](string w) { sort(w.begin(), w.end()); return w; };
    vector<string> result;                       // survivors
    for (const string& w : words) {
        // drop w if it is an anagram of the last kept word
        if (!result.empty() && sig(result.back()) == sig(w)) {
            continue;
        }
        result.push_back(w);                     // keep this word
    }
    return result;
}

Explanation

The deletions only ever compare a word to the one immediately before it, and the problem guarantees the order of operations does not matter. That lets us collapse the whole process into a single left-to-right scan.

For each word we compute a signature: its letters sorted alphabetically. Two words are anagrams exactly when their signatures are equal (a sorted multiset of characters is a canonical form). For example "abba", "baba", and "bbaa" all sort to "aabb".

We keep a result list of survivors. When we reach a new word, we compare its signature to the signature of the last word already in result. If they match, this word is an anagram of a survivor and would be deleted, so we skip it. Otherwise it begins a new run and we append it.

Because deletions cascade — once "baba" is removed, "bbaa" is then adjacent to "abba" — comparing against the last survivor (not the raw previous word) is what makes a single pass correct.

Example: ["abba","baba","bbaa","cd","cd"]. "abba" is kept. "baba" and "bbaa" share its signature aabb, so both are skipped. "cd" (signature cd) differs, so it is kept; the second "cd" matches it and is skipped. Result: ["abba","cd"].

Time: O(n · L log L) Space: O(L)