Find Resultant Array After Removing Anagrams solution and explanation
IBM
Google
9 more videos on this problem
Find Resultant Array After Removing Anagrams | Multiple Approach | Leetcode 2273 | codestorywithMIKcodestorywithMIK · 17:42 · 4K views
Find Resultant Array After Removing Anagrams | Leetcode 2273 | Two Pointer | Live coding sessionCoding Decoded · 8:03 · 2K views
2273. Find Resultant Array After Removing Anagrams (Leetcode Easy)Programming Live with Larry · 2:55 · 1K views
2273. Find Resultant Array After Removing Anagrams | Leetcode Daily - PythonLeetcode Daily · 6:36 · 495 views
Find Resultant Array After Removing Anagrams | LeetCode 2273 | Beginner Friendly ProblemSanyam IIT Guwahati · 7:53 · 282 views
2273 Find Resultant Array After Removing AnagramsJasmeet Singh · 9:14 · 226 views
Find Resultant Array After Removing Anagrams | LeetCode 2273 - Pythonimpoldev · 8:35 · 184 views
2273 Find Resultant Array After Removing Anagrams LeetCode Contest 293 | Easy | JavascriptXyzAbc · 7:24 · 173 views
2273 find resultant array after removing anagrams[CE] Code Engineering · 28:15 · 118 views
LeetCode Daily 2273 | Find Resultant Array After Removing Anagrams | Easy | Solution WalkthroughDaily Dose Of LeetCode · 16:06 · 104 views
The 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".
Example 1:
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:
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 <= 1001 <= words[i].length <= 10words[i]consists of lowercase English letters.
Approach overview
Problem Overview: You are given an array of words. If two adjacent words are anagrams, remove the later one. Continue scanning left to right and keep only the first occurrence in each consecutive anagram group. The final result is the array of remaining words after these removals.
Approach 1: Sort and Compare (Time: O(n * k log k), Space: O(k))
The most common strategy is to normalize each word so all anagrams share the same representation. Sort the characters of every word using sort(). Two strings are anagrams if their sorted forms are identical. Iterate through the array once, compute the sorted version of the current word, and compare it with the sorted version of the previously accepted word. If they match, skip the current word; otherwise append it to the result array. Sorting each string costs O(k log k) where k is the word length, and you perform this for n words, resulting in O(n * k log k) time. Space usage stays O(k) for the temporary sorted representation. This approach is simple, reliable, and commonly used for string anagram detection problems.
Approach 2: Frequency Count and Compare (Time: O(n * k), Space: O(26))
A more efficient approach avoids sorting entirely. Instead, build a frequency vector for each word representing counts of characters a–z. Two words are anagrams if their frequency arrays match exactly. While iterating through the input, compute the frequency array for the current word and compare it with the frequency array of the last accepted word. If the arrays are identical, the current word is an anagram of the previous one and should be skipped. Otherwise add it to the result and update the stored frequency array. Counting characters requires O(k) time per word, so the full traversal runs in O(n * k). Space complexity remains O(26) (constant) for the frequency vector. This technique is common in problems involving hash tables or character counting and avoids the overhead of sorting.
Both approaches rely on the same insight: you only compare the current word with the previously kept word, not with the entire result array. The constraint that removals happen only for adjacent anagrams simplifies the logic to a single linear pass over the array.
Recommended for interviews: The frequency-count solution is usually preferred because it improves the complexity from O(n * k log k) to O(n * k). Still, explaining the sorting approach first demonstrates understanding of the classic sorting-based anagram check. Transitioning to frequency counting shows optimization and stronger algorithmic thinking.
Approach 1: Sort and Compare
This approach involves sorting each word in the array and comparing adjacent sorted words. If two adjacent sorted words are equal, they are anagrams and we remove the second word. Iterate through the array, adjusting the index when necessary due to removals.
def removeAnagrams(words):
i = 1
while i < len(words):
if sorted(words[i]) == sorted(words[i - 1]):
words.pop(i)
else:
i += 1
return words
words = ["abba", "baba", "bbaa", "cd", "cd"]
result = removeAnagrams(words)
print(result)import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static List<String> removeAnagrams(String[] words) {
List<String> result = new ArrayList<>();
for (String word : words) result.add(word);
for (int i = 1; i < result.size(); i++) {
char[] prevArr = result.get(i - 1).toCharArray();
char[] currArr = result.get(i).toCharArray();
Arrays.sort(prevArr);
Arrays.sort(currArr);
if (Arrays.equals(prevArr, currArr)) {
result.remove(i);
i--;
}
}
return result;
}
public static void main(String[] args) {
String[] words = {"abba", "baba", "bbaa", "cd", "cd"};
List<String> result = removeAnagrams(words);
for (String word : result) {
System.out.print(word + " ");
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> removeAnagrams(vector<string>& words) {
for (int i = 1; i < words.size(); ++i) {
string prev = words[i - 1];
string current = words[i];
sort(prev.begin(), prev.end());
sort(current.begin(), current.end());
if (prev == current) {
words.erase(words.begin() + i);
--i;
}
}
return words;
}
int main() {
vector<string> words = {"abba", "baba", "bbaa", "cd", "cd"};
vector<string> result = removeAnagrams(words);
for (const string& word : result) {
cout << word << " ";
}
return 0;
}function removeAnagrams(words) {
let i = 1;
while (i < words.length) {
if (words[i].split('').sort().join('') === words[i - 1].split('').sort().join('')) {
words.splice(i, 1);
} else {
i++;
}
}
return words;
}
let words = ["abba", "baba", "bbaa", "cd", "cd"];
console.log(removeAnagrams(words));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmpfunc(const void *a, const void *b) {
return (*(char *)a - *(char *)b);
}
char **remove_anagrams(char **words, int wordsSize, int *returnSize) {
int i, j, k;
for (i = 1; i < wordsSize; i++) {
char *word1 = strdup(words[i - 1]);
char *word2 = strdup(words[i]);
qsort(word1, strlen(word1), sizeof(char), cmpfunc);
qsort(word2, strlen(word2), sizeof(char), cmpfunc);
if (strcmp(word1, word2) == 0) {
free(words[i]);
for (j = i; j < wordsSize - 1; j++) {
words[j] = words[j + 1];
}
wordsSize--;
i--;
}
free(word1);
free(word2);
}
*returnSize = wordsSize;
return words;
}
int main() {
char *words[] = {"abba", "baba", "bbaa", "cd", "cd"};
int wordsSize = 5;
int returnSize;
char **result = remove_anagrams(words, wordsSize, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Program {
public static List<string> RemoveAnagrams(string[] words) {
List<string> result = new List<string>(words);
for (int i = 1; i < result.Count; i++) {
char[] prevArr = result[i - 1].ToCharArray();
char[] currArr = result[i].ToCharArray();
Array.Sort(prevArr);
Array.Sort(currArr);
if (new string(prevArr) == new string(currArr)) {
result.RemoveAt(i);
i--;
}
}
return result;
}
public static void Main() {
string[] words = {"abba", "baba", "bbaa", "cd", "cd"};
List<string> result = RemoveAnagrams(words);
foreach (var word in result) {
Console.Write(word + " ");
}
}
}This Python implementation removes anagrams by using sorted() to transform words into comparable forms. The loop conditionally retains non-anagram words, utilizing list's pop method upon detection.
Time Complexity: O(n * m log m) due to sorting words.
Space Complexity: O(n * m) storing sorted characters as lists.
Approach 2: Frequency Count and Compare
This method involves counting the frequency of each letter for the words being compared. Adjacency checks then use these frequency dictionaries (or arrays) to decide if words are anagram pairs, which leads to the removal of one.
def removeAnagrams(words):
def is_anagram(s1, s2):
from collections import Counter
return Counter(s1) == Counter(s2)
i = 1
while i < len(words):
if is_anagram(words[i], words[i - 1]):
words.pop(i)
else:
i += 1
return words
words = ["abba", "baba", "bbaa", "cd", "cd"]
result = removeAnagrams(words)
print(result)import java.util.ArrayList;
import java.util.List;
public class Main {
public static boolean isAnagram(String s1, String s2) {
int[] count = new int[26];
for (char c : s1.toCharArray()) count[c - 'a']++;
for (char c : s2.toCharArray()) count[c - 'a']--;
for (int i : count) {
if (i != 0) return false;
}
return true;
}
public static List<String> removeAnagrams(String[] words) {
List<String> result = new ArrayList<>();
for (String word : words) result.add(word);
for (int i = 1; i < result.size(); i++) {
if (isAnagram(result.get(i - 1), result.get(i))) {
result.remove(i);
i--;
}
}
return result;
}
public static void main(String[] args) {
String[] words = {"abba", "baba", "bbaa", "cd", "cd"};
List<String> result = removeAnagrams(words);
for (String word : result) {
System.out.print(word + " ");
}
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isAnagram(const string& s1, const string& s2) {
int count[26] = {0};
for (char c : s1) count[c - 'a']++;
for (char c : s2) count[c - 'a']--;
for (int n : count) {
if (n != 0) return false;
}
return true;
}
vector<string> removeAnagrams(vector<string>& words) {
for (int i = 1; i < words.size(); ++i) {
if (isAnagram(words[i - 1], words[i])) {
words.erase(words.begin() + i);
--i;
}
}
return words;
}
int main() {
vector<string> words = {"abba", "baba", "bbaa", "cd", "cd"};
vector<string> result = removeAnagrams(words);
for (const string& word : result) {
cout << word << " ";
}
return 0;
}function removeAnagrams(words) {
const isAnagram = (s1, s2) => {
const count = Array(26).fill(0);
for (let i = 0; i < s1.length; i++) count[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;
for (let i = 0; i < s2.length; i++) count[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;
return count.every(v => v === 0);
}
let i = 1;
while (i < words.length) {
if (isAnagram(words[i], words[i - 1])) {
words.splice(i, 1);
} else {
i++;
}
}
return words;
}
let words = ["abba", "baba", "bbaa", "cd", "cd"];
console.log(removeAnagrams(words));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int isAnagram(const char *s1, const char *s2) {
int count[26] = {0};
while (*s1) count[*s1++ - 'a']++;
while (*s2) count[*s2++ - 'a']--;
for (int i = 0; i < 26; i++) {
if (count[i] != 0) return 0;
}
return 1;
}
char **remove_anagrams(char **words, int wordsSize, int *returnSize) {
int i, j;
for (i = 1; i < wordsSize; ++i) {
if (isAnagram(words[i - 1], words[i])) {
free(words[i]);
for (j = i; j < wordsSize - 1; j++) {
words[j] = words[j + 1];
}
wordsSize--;
i--;
}
}
*returnSize = wordsSize;
return words;
}
int main() {
char *words[] = {"abba", "baba", "bbaa", "cd", "cd"};
int wordsSize = 5;
int returnSize;
char **result = remove_anagrams(words, wordsSize, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Program {
public static bool IsAnagram(string s1, string s2) {
int[] count = new int[26];
foreach (var c in s1) count[c - 'a']++;
foreach (var c in s2) count[c - 'a']--;
foreach (var x in count) {
if (x != 0) return false;
}
return true;
}
public static List<string> RemoveAnagrams(string[] words) {
List<string> result = new List<string>(words);
for (int i = 1; i < result.Count; i++) {
if (IsAnagram(result[i - 1], result[i])) {
result.RemoveAt(i);
i--;
}
}
return result;
}
public static void Main() {
string[] words = {"abba", "baba", "bbaa", "cd", "cd"};
List<string> result = RemoveAnagrams(words);
foreach (var word in result) {
Console.Write(word + " ");
}
}
}This Python solution uses Counter from the collections module to derive frequency counts that detect anagrams between adjacent words.
Time Complexity: O(n * m) as character counting operates for each word pair.
Space Complexity: O(n * m) storing counts in dictionary objects.
Approach 3: Simulation
We first add words[0] to the answer array, then traverse from words[1]. If words[i - 1] and words[i] are not anagrams, we add words[i] to the answer array.
The problem is converted to determining whether two strings are anagrams. We define a helper function check(s, t) to achieve this. If s and t are not anagrams, we return true; otherwise, we return false.
In the function check(s, t), we first check if the lengths of s and t are equal. If they are not, we return true. Otherwise, we use an array cnt of length 26 to count the occurrences of each character in s, then traverse each character in t and decrement cnt[c] by 1. If cnt[c] is less than 0, we return true. If we traverse all characters in t without issues, it means s and t are anagrams, and we return false.
The time complexity is O(L), and the space complexity is O(|\Sigma|). Here, L is the length of the array words, and \Sigma is the character set, which is lowercase English letters, so |\Sigma| = 26.
function removeAnagrams(words: string[]): string[] {
const ans: string[] = [words[0]];
const check = (s: string, t: string): boolean => {
if (s.length !== t.length) {
return true;
}
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
++cnt[c.charCodeAt(0) - 97];
}
for (const c of t) {
if (--cnt[c.charCodeAt(0) - 97] < 0) {
return true;
}
}
return false;
};
for (let i = 1; i < words.length; ++i) {
if (check(words[i - 1], words[i])) {
ans.push(words[i]);
}
}
return ans;
}func removeAnagrams(words []string) []string {
ans := []string{words[0]}
check := func(s, t string) bool {
if len(s) != len(t) {
return true
}
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for _, c := range t {
cnt[c-'a']--
if cnt[c-'a'] < 0 {
return true
}
}
return false
}
for i, t := range words[1:] {
if check(words[i], t) {
ans = append(ans, t)
}
}
return ans
}impl Solution {
pub fn remove_anagrams(words: Vec<String>) -> Vec<String> {
fn check(s: &str, t: &str) -> bool {
if s.len() != t.len() {
return true;
}
let mut cnt = [0; 26];
for c in s.bytes() {
cnt[(c - b'a') as usize] += 1;
}
for c in t.bytes() {
let idx = (c - b'a') as usize;
cnt[idx] -= 1;
if cnt[idx] < 0 {
return true;
}
}
false
}
let mut ans = vec![words[0].clone()];
for i in 1..words.len() {
if check(&words[i - 1], &words[i]) {
ans.push(words[i].clone());
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Compare | Time Complexity: O(n * m log m) due to sorting words. |
| Frequency Count and Compare | Time Complexity: O(n * m) as character counting operates for each word pair. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Compare | O(n * k log k) | O(k) | Simple implementation and common approach when checking anagrams with sorting |
| Frequency Count and Compare | O(n * k) | O(26) | Optimal solution when words contain lowercase letters and sorting overhead should be avoided |
Frequently asked questions
Is Find Resultant Array After Removing Anagrams easy or hard?
The problem is classified as Easy on LeetCode with an acceptance rate around 70%. The challenge mainly involves recognizing that only adjacent words need to be checked and applying a standard anagram detection technique.
Find Resultant Array After Removing Anagrams Python/Java solution
In Python or Java, iterate through the words and compute either the sorted version of the string or a frequency array of characters. Compare it with the previous stored representation. If they match, skip the word; otherwise add it to the result list.
How to solve Find Resultant Array After Removing Anagrams in O(n)?
Strict O(n) is not possible because each word must be inspected character by character. The closest optimal solution is O(n * k) using a character frequency array. For each word, compute a 26-element count and compare it with the previous word's count to detect anagrams.
What is the best approach for Find Resultant Array After Removing Anagrams?
The frequency count approach is typically the best solution. Build a 26-length character frequency array for each word and compare it with the previous word's frequency array. This avoids sorting and runs in O(n * k) time where n is the number of words and k is the word length.
Is Find Resultant Array After Removing Anagrams asked at Google/Amazon/Meta?
Anagram detection and string normalization problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying techniques such as sorting strings or using character frequency arrays are commonly tested.
What data structure is used in Find Resultant Array After Removing Anagrams?
The solution primarily uses arrays and character frequency counters. A fixed-size array of length 26 is commonly used to track letter counts. Some implementations also rely on sorting utilities and simple array traversal.
What is the time complexity of Find Resultant Array After Removing Anagrams?
The sorting approach runs in O(n * k log k) because each word must be sorted before comparison. The optimized frequency counting approach reduces this to O(n * k) by counting characters instead of sorting them. Space complexity is O(k) for sorting or O(26) for the frequency array.