Problem Description

Given a 0-indexed string array words, you are to process the array such that you remove any string that is an anagram of the string immediately before it. An anagram is a word or phrase formed by rearranging the letters of another, such as "abc" and "cab".

You must return the resultant array after all required removals. The removal should be performed in order: for each string, check whether it is an anagram of the previous string in the current result; if so, skip it, otherwise add it to the result.

• Each string consists of lowercase English letters.
• Only consecutive anagrams are to be removed (i.e., non-consecutive anagrams do not affect each other).
• There is always at least one string in the input.
• The output must preserve the original order of the remaining strings.

Thought Process

To solve this problem, let's first understand what it means for two words to be anagrams: they must contain the same characters in any order. Our task is to iterate through the words array and, for each word, check if it is an anagram of the previous word in our result array. If so, we skip it; otherwise, we keep it.

The brute-force approach would be, for each word, to compare it with the previous word by sorting both and checking for equality. However, this could be inefficient if the words are long or the list is large. We can optimize by only comparing each word to the last unique word added to the result, and by using a canonical form (such as a sorted string or a frequency count) to represent each word for quick comparison.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Initialize the result: Start with an empty list to hold the processed words.
2. Iterate through the input: For each word in words, do the following:
   • If the result list is empty, add the word to the result.
   • Otherwise, compare the current word to the last word in the result.
3. Check for anagram: To check if two words are anagrams, convert both words to their sorted character form (e.g., "abc" for both "abc" and "cab").
4. Decision: If the sorted forms are the same, skip the word; if not, add it to the result.
5. Return the result: After processing all words, return the result list.

This approach is efficient because:

• We only compare each word to the immediate previous result, not all previous words.
• Sorting a small string is fast, and we do it only once per word.

Example Walkthrough

Let's walk through an example:

Input: ["abba", "baba", "bbaa", "cd", "cd"]

1. result = []
2. Process "abba":
   • Result is empty, so add "abba".
   • result = ["abba"]
3. Process "baba":
   • Sort "baba" → "aabb"
   • Sort last in result ("abba") → "aabb"
   • They are the same, so skip "baba".
4. Process "bbaa":
   • Sort "bbaa" → "aabb"
   • Sort last in result ("abba") → "aabb"
   • They are the same, so skip "bbaa".
5. Process "cd":
   • Sort "cd" → "cd"
   • Sort last in result ("abba") → "aabb"
   • They are different, so add "cd".
   • result = ["abba", "cd"]
6. Process "cd":
   • Sort "cd" → "cd"
   • Sort last in result ("cd") → "cd"
   • They are the same, so skip "cd".

Final Output: ["abba", "cd"]

Code Implementation

class Solution:
    def removeAnagrams(self, words):
        result = []
        prev_sorted = ""
        for word in words:
            sorted_word = ''.join(sorted(word))
            if not result or sorted_word != prev_sorted:
                result.append(word)
                prev_sorted = sorted_word
        return result
      

class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> result;
        string prev_sorted = "";
        for (const string& word : words) {
            string sorted_word = word;
            sort(sorted_word.begin(), sorted_word.end());
            if (result.empty() || sorted_word != prev_sorted) {
                result.push_back(word);
                prev_sorted = sorted_word;
            }
        }
        return result;
    }
};
      

import java.util.*;
class Solution {
    public List<String> removeAnagrams(String[] words) {
        List<String> result = new ArrayList<>();
        String prevSorted = "";
        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String sortedWord = new String(chars);
            if (result.isEmpty() || !sortedWord.equals(prevSorted)) {
                result.add(word);
                prevSorted = sortedWord;
            }
        }
        return result;
    }
}
      

var removeAnagrams = function(words) {
    let result = [];
    let prevSorted = "";
    for (let word of words) {
        let sortedWord = word.split('').sort().join('');
        if (result.length === 0 || sortedWord !== prevSorted) {
            result.push(word);
            prevSorted = sortedWord;
        }
    }
    return result;
};
      

Time and Space Complexity

Brute-force approach:

• For each word, compare with all previous words in the result, sorting each time.
• Time complexity: O(N^2 * L log L), where N is the number of words and L is the average word length.
• Space complexity: O(N * L) for storing the result and intermediate sorted words.

• We only compare each word with the last word in the result.
• Sorting each word: O(L log L) per word, for N words: O(N * L log L).
• Space complexity: O(N * L) for storing the result array and the sorted forms.

The optimized approach is much more efficient, especially for large input sizes.

Summary

In this problem, we efficiently remove consecutive anagrams from an array of strings by comparing each word's sorted form to that of the last unique word added to our result. This approach ensures only necessary comparisons and leverages sorting for quick anagram detection. The solution is both simple and effective, using fundamental data structures and string processing techniques to achieve optimal performance.