Finding the Resultant Array After Removing Anagrams
On this page 
Problem Statement Solution 1: Using Stack for Anagram Removal Solution 2: Using Index-Based Traversal for Anagram Removal Solution 3: Using Set and Helper Function for Anagram Removal Solution 4: Using Sorting and Comparison for Anagram Removal Solution 5: Using Linked List and Sorting for Anagram Removal More Problems Solutions
Problem Statement
You are given an array of strings called words, where each string consists of lowercase English letters.
Your task is to perform the following operation:
In each operation, select any index
isuch that0 < i < words.length, and if the string at indexiis an anagram of the string at indexi - 1, delete the string at indexifrom the array. Continue performing this operation as long as you can find such indices.
An anagram is a word or phrase formed by rearranging the letters of another word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".
Objective: Return the array after performing all possible operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same final result.
Example 1
Input: words = ["abba","baba","bbaa","cd","cd"]
Output: ["abba","cd"]
Example 2
Input: words = ["a","b","c","d","e"]
Output: ["a","b","c","d","e"]
Constraints
1 <= words.length <= 100: The length of the arraywordsis between 1 and 100.1 <= words[i].length <= 10: The length of each string in the array is between 1 and 10 characters.words[i]consists only of lowercase English letters.
Solution 1: Using Stack for Anagram Removal
function removeAnagramsStack(words) {
let stack = [];
for (let i = words.length - 1; i >= 0; i--) {
let currentWord = words[i];
// Remove elements from stack while the top of the stack is an anagram of the current word
while (stack.length > 0 && areAnagrams(stack[stack.length - 1], currentWord)) {
stack.pop();
}
stack.push(currentWord);
}
// Convert stack to result list
let result = [];
while (stack.length > 0) {
result.push(stack.pop());
}
return result;
}
function areAnagrams(word1, word2) {
if (word1.length !== word2.length) return false;
let counts = new Array(26).fill(0);
for (let char of word1) {
counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let char of word2) {
counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]--;
}
return counts.every(count => count === 0);
}
const words1 = ["abba","baba","bbaa","cd","cd"];
removeAnagramsStack(words1); //output: ["abba","cd"]
const words2 = ["a","b","c","d","e"];
removeAnagramsStack(words2); //output: ["a","b","c","d","e"]
Solution 2: Using Index-Based Traversal for Anagram Removal
function removeAnagramsIndexBased(words) {
let result = [];
let n = words.length;
let i = 0;
while (i < n) {
let j = i + 1;
// Find the next index where words[i] and words[j] are not anagrams
while (j < n && areAnagrams1(words[i], words[j])) {
j++;
}
// Add the current word to the result list
result.push(words[i]);
// Move to the next set of words
i = j;
}
return result;
}
function areAnagrams1(word1, word2) {
if (word1.length !== word2.length) return false;
let counts = new Array(26).fill(0);
for (let char of word1) {
counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let char of word2) {
counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]--;
}
return counts.every(count => count === 0);
}
const words1 = ["abba","baba","bbaa","cd","cd"];
removeAnagramsIndexBased(words1); //output: ["abba","cd"]
const words2 = ["a","b","c","d","e"];
removeAnagramsIndexBased(words2); //output: ["a","b","c","d","e"]
Solution 3: Using Set and Helper Function for Anagram Removal
function removeAnagramsSet(words) {
let set = new Set();
while (set.size < words.length) {
let found = false;
for (let i = 0; i < words.length; i++) {
if (set.has(i)) {
continue;
}
if (i === words.length - 1) {
break;
}
let next = findNextIndex(set, i + 1, words.length - 1);
if (next === -1) {
break;
}
if (areAnagrams2(words[i], words[next])) {
set.add(next);
found = true;
}
}
if (!found) {
break;
}
}
let result = [];
for (let i = 0; i < words.length; i++) {
if (!set.has(i)) {
result.push(words[i]);
}
}
return result;
}
function findNextIndex(set, start, end) {
for (let i = start; i <= end; i++) {
if (!set.has(i)) {
return i;
}
}
return -1;
}
function areAnagrams2(word1, word2) {
if (word1.length !== word2.length) return false;
let counts = new Array(256).fill(0);
for (let char of word1) {
counts[char.charCodeAt(0)]++;
}
for (let char of word2) {
counts[char.charCodeAt(0)]--;
}
return counts.every(count => count === 0);
}
const words1 = ["abba","baba","bbaa","cd","cd"];
removeAnagramsSet(words1); //output: ["abba","cd"]
const words2 = ["a","b","c","d","e"];
removeAnagramsSet(words2); //output: ["a","b","c","d","e"]
Solution 4: Using Sorting and Comparison for Anagram Removal
function removeAnagramsSorting(words) {
let result = [];
let temp = "";
for (let word of words) {
// Convert word to a character array, sort it, and then convert back to a string
let sortedWord = word.split('').sort().join('');
// Add word to result if it's not an anagram of the previous word
if (sortedWord !== temp) {
result.push(word);
}
// Update temp to the current sorted word
temp = sortedWord;
}
return result;
}
const words1 = ["abba","baba","bbaa","cd","cd"];
removeAnagramsSorting(words1); //output: ["abba","cd"]
const words2 = ["a","b","c","d","e"];
removeAnagramsSorting(words2); //output: ["a","b","c","d","e"]
Solution 5: Using Linked List and Sorting for Anagram Removal
function removeAnagramsLinkedList(words) {
let result = [];
let lastAnagramStr = null;
for (let word of words) {
// Convert word to a character array, sort it, and then convert back to a string
let sortedWord = word.split('').sort().join('');
// Check if the current sorted word is the same as the last one
if (sortedWord === lastAnagramStr) {
continue;
}
// Update lastAnagramStr and add the word to the result list
lastAnagramStr = sortedWord;
result.push(word);
}
return result;
}
const words1 = ["abba","baba","bbaa","cd","cd"];
removeAnagramsLinkedList(words1); //output: ["abba","cd"]
const words2 = ["a","b","c","d","e"];
removeAnagramsLinkedList(words2); //output: ["a","b","c","d","e"]