Find Resultant Array After Removing Anagrams

Find Resultant Array After Removing Anagrams - 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".

Input & Output

Example 1 — Basic Anagram Removal

$ Input: words = ["abba","baba","bbaa","cd","cd"]

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

💡 Note: "baba" is anagram of "abba" (removed), "bbaa" is anagram of "abba" (removed), second "cd" is anagram of first "cd" (removed)

Example 2 — No Anagrams

$ Input: words = ["a","b","c"]

› Output: ["a","b","c"]

💡 Note: No adjacent words are anagrams, so all words remain in the result

Example 3 — All Same Letters

$ Input: words = ["abc","bca","cab"]

› Output: ["abc"]

💡 Note: "bca" is anagram of "abc" (removed), "cab" would be anagram of "abc" (removed)

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 10
words[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Array

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

Process

Remove words that are anagrams of their previous word

Output

["abba","cd"] - only non-anagram words remain

Key Takeaway

🎯 Key Insight: Sort characters to create a canonical form that makes anagram comparison O(1) after preprocessing

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that two words are anagrams if they contain the same characters with the same frequencies. The optimal approach sorts the characters in each word to create a canonical form, then compares adjacent words. Time: O(n × m log m), Space: O(m) where n is number of words and m is average word length.

Common Approaches

Approach	Time	Space	Notes
✓ Sorted String Comparison	O(n × m log m)	O(m)	Sort characters in each word to create canonical form for anagram comparison
Brute Force Character Comparison	O(n × m)	O(1)	Compare each word with its previous word by counting character frequencies

Sorted String Comparison — Algorithm Steps

Sort characters in each word to get canonical form
Compare sorted forms of adjacent words
Remove word if sorted forms match
Continue until no more removals possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Characters

Sort each word's characters alphabetically

Compare Sorted

Compare sorted forms of adjacent words

Filter Result

Keep words with different sorted forms

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

void getSorted(char* word, char* sorted) {
    strcpy(sorted, word);
    qsort(sorted, strlen(sorted), sizeof(char), compare);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char words[1000][100];
    int wordCount = 0;
    
    char* token = strtok(line, "[\",]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            strcpy(words[wordCount++], token);
        }
        token = strtok(NULL, "[\",]");
    }
    
    char result[1000][100];
    int resultCount = 1;
    strcpy(result[0], words[0]);
    
    char prevSorted[100], currSorted[100];
    getSorted(words[0], prevSorted);
    
    for (int i = 1; i < wordCount; i++) {
        getSorted(words[i], currSorted);
        if (strcmp(currSorted, prevSorted) != 0) {
            strcpy(result[resultCount++], words[i]);
            strcpy(prevSorted, currSorted);
        }
    }
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("\"%s\"", result[i]);
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m log m)

n words × m log m for sorting characters in each word

⚡ Linearithmic

Space Complexity

O(m)

Space for sorted string of length m

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sorted String Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler