algoadvance

Leetcode 2273. Find Resultant Array After Removing Anagrams

Problem Statement

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters. In one operation, you can select any index i and remove words[i] if words[i - 1] and words[i] are anagrams of each other. You need to return the resultant array after applying the operation any number of times.

Clarifying Questions

1. Question: Can words contain duplicate strings which are not at adjacent positions?
   • Answer: Yes, words can contain duplicate strings, but we only consider removal when adjacent strings are anagrams.
2. Question: Are we allowed to directly create a new array for result or do we need to do in-place modification?
   • Answer: Direct creation of a new array is acceptable.
3. Question: Is the order of words important in the resultant array?
   • Answer: Yes, we need to preserve the original order of words that are not removed.

Strategy

1. Comparison function: We need a function to compare if two strings are anagrams. One efficient way is to sort both strings and check if they are equal.

2. Iteration: Iterate through the list of words and build the resultant array by only adding words that are not anagrams of the previous word in the resultant array.

3. Implementation Steps:

   • Define a helper function to check if two words are anagrams of each other using sorted strings.
   • Iterate through the list words, and at each step, check if the current word is an anagram of the last word added to the resultant array.
   • If it is not an anagram, add the current word to the resultant array.

Time Complexity

• Sorting each word takes (O(k \log k)) where (k) is the length of the word.
• Since we compare each word once, the overall time complexity is (O(n \cdot k \log k)) where (n) is the number of words.

Code

#include <vector>
#include <string>
#include <algorithm> // for sort
#include <iostream>

// Helper function to check if two strings are anagrams
bool areAnagrams(const std::string& s1, const std::string& s2) {
    if (s1.length() != s2.length()) return false;
    // Sort both strings and compare
    std::string sorted_s1 = s1;
    std::string sorted_s2 = s2;
    std::sort(sorted_s1.begin(), sorted_s1.end());
    std::sort(sorted_s2.begin(), sorted_s2.end());
    return sorted_s1 == sorted_s2;
}

std::vector<std::string> removeAnagrams(std::vector<std::string>& words) {
    if (words.empty()) return {};
    std::vector<std::string> result;
    result.push_back(words[0]);
    for (size_t i = 1; i < words.size(); ++i) {
        if (!areAnagrams(result.back(), words[i])) {
            result.push_back(words[i]);
        }
    }
    return result;
}

int main() {
    std::vector<std::string> words = {"abba", "baba", "bbaa", "cd", "cd"};
    std::vector<std::string> result = removeAnagrams(words);

    std::cout << "Resultant words:";
    for (const auto& word : result) {
        std::cout << " " << word;
    }
    std::cout << std::endl;
    return 0;
}

Explanation:

1. areAnagrams Function: Checks if two strings are anagrams by sorting and comparing them.
2. removeAnagrams Function:
   • Initialize the result with the first word.
   • Iterate through the words, adding each word to the result if it is not an anagram of the last word in the result.
3. Main Function: Demonstrates usage with an example list of words.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?