Problem

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams , and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: words = ["abba","baba","bbaa","cd","cd"]
Output: ["abba","cd"]
Explanation:
One of the ways we can obtain the resultant array is by using the following operations:
- Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","baba","cd","cd"].
- Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1].
  Now words = ["abba","cd","cd"].
- Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","cd"].
We can no longer perform any operations, so ["abba","cd"] is the final answer.

Example 2

1
2
3
4

Input: words = ["a","b","c","d","e"]
Output: ["a","b","c","d","e"]
Explanation:
No two adjacent strings in words are anagrams of each other, so no operations are performed.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.

Solution

Method 1 – Stack with Anagram Check

Intuition

To remove consecutive anagrams, we can process the words from left to right, keeping only the first word in each group of consecutive anagrams. We use a stack to keep the result and compare each word with the last word in the stack by checking if their sorted characters are equal.

Approach

  1. Initialize an empty stack (or result list).
  2. For each word in words:
    • If the stack is empty or the sorted version of the current word is not equal to the sorted version of the last word in the stack, append the word to the stack.
    • Otherwise, skip the word (it’s a consecutive anagram).
  3. Return the stack as the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> ans;
        for (auto& w : words) {
            if (ans.empty() || isAnagram(ans.back(), w) == false) ans.push_back(w);
        }
        return ans;
    }
private:
    bool isAnagram(const string& a, const string& b) {
        string sa = a, sb = b;
        sort(sa.begin(), sa.end());
        sort(sb.begin(), sb.end());
        return sa == sb;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func removeAnagrams(words []string) []string {
    ans := []string{}
    for _, w := range words {
        if len(ans) == 0 || !isAnagram(ans[len(ans)-1], w) {
            ans = append(ans, w)
        }
    }
    return ans
}

func isAnagram(a, b string) bool {
    sa := []rune(a)
    sb := []rune(b)
    sort.Slice(sa, func(i, j int) bool { return sa[i] < sa[j] })
    sort.Slice(sb, func(i, j int) bool { return sb[i] < sb[j] })
    return string(sa) == string(sb)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public List<String> removeAnagrams(String[] words) {
        List<String> ans = new ArrayList<>();
        for (String w : words) {
            if (ans.isEmpty() || !isAnagram(ans.get(ans.size()-1), w)) ans.add(w);
        }
        return ans;
    }
    private boolean isAnagram(String a, String b) {
        char[] ca = a.toCharArray(), cb = b.toCharArray();
        Arrays.sort(ca); Arrays.sort(cb);
        return Arrays.equals(ca, cb);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun removeAnagrams(words: Array<String>): List<String> {
        val ans = mutableListOf<String>()
        for (w in words) {
            if (ans.isEmpty() || !isAnagram(ans.last(), w)) ans.add(w)
        }
        return ans
    }
    private fun isAnagram(a: String, b: String): Boolean {
        return a.toCharArray().sorted() == b.toCharArray().sorted()
    }
}
1
2
3
4
5
6
7

class Solution:
    def removeAnagrams(self, words: list[str]) -> list[str]:
        ans = []
        for w in words:
            if not ans or sorted(ans[-1]) != sorted(w):
                ans.append(w)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn remove_anagrams(words: Vec<String>) -> Vec<String> {
        let mut ans = Vec::new();
        for w in words {
            if ans.is_empty() || !is_anagram(&ans[ans.len()-1], &w) {
                ans.push(w);
            }
        }
        ans
    }
}
fn is_anagram(a: &str, b: &str) -> bool {
    let mut ca: Vec<char> = a.chars().collect();
    let mut cb: Vec<char> = b.chars().collect();
    ca.sort_unstable();
    cb.sort_unstable();
    ca == cb
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    removeAnagrams(words: string[]): string[] {
        const ans: string[] = [];
        for (const w of words) {
            if (ans.length === 0 || !this.isAnagram(ans[ans.length-1], w)) ans.push(w);
        }
        return ans;
    }
    private isAnagram(a: string, b: string): boolean {
        return a.split('').sort().join('') === b.split('').sort().join('');
    }
}

Complexity

  • ⏰ Time complexity: O(n * k log k), where n is the number of words and k is the maximum word length, due to sorting each word for anagram checking.
  • 🧺 Space complexity: O(n * k), for the answer array and temporary sorted strings.