2273. Find Resultant Array After Removing Anagrams

Problem Description

The problem presents us with an array of strings named words, where each element is a word composed of lowercase English letters. The main objective is to repeatedly delete words from the array under a specific condition: a word should be deleted if it is an anagram of the word preceding it. The index i of the word to be deleted must satisfy the condition that 0 < i < words.length, meaning that the first word can never be deleted, and we must also have at least two words to proceed with a deletion.

An anagram is defined as a rearrangement of the letters of one word to form another word, with the condition that all original letters are used exactly once. For example, "listen" and "silent" are anagrams, as both contain the same letters in different orders.

This task is to be repeated until there are no more consecutive words that are anagrams of each other. At that point, we should return the final list of words.

Intuition

The intuition behind the provided solution comes from the definition of anagrams. If two words are anagrams of each other, they will have the same letters in some order. Therefore, by sorting the letters of each word, we can easily compare them to check if they are anagrams.

The implementation uses a list comprehension, which is a concise way to generate a new list based on an existing list. For the current word w in words, two conditions are checked:

1. If w is the first word, it is included because the first word can never be an anagram of a preceding word (as there is no preceding word).
2. If w is not the first word, it is included if and only if its sorted form is different from the sorted form of the previous word in the list. This check ensures that w is not an anagram of the word immediately before it.

The solution does not require any additional loops or recursive calls because the problem guarantees that the order of deletions does not affect the final list of words that remain. Therefore, sequentially iterating over the list from start to finish is sufficient for finding the solution.

Learn more about Sorting patterns.

Solution Approach

The solution utilizes a Python list comprehension to succinctly filter out the unwanted words that are anagrams of their immediate predecessors. Let's dive into the implementation detail:

1. A for loop is created by the enumerate function, which provides both the index i and the word w from the words list. The use of enumerate is essential here as we need to access the previous word to perform the anagram check.

2. The list comprehension iterates over each word (w) and its index (i) in the list words. The condition i == 0 or sorted(w) != sorted(words[i - 1]) is the heart of this implementation, which serves two purposes:

   • i == 0: It ensures that the first word is always included in the final list because there is no word before it to check against for anagrams.
   • sorted(w) != sorted(words[i - 1]): For any word that is not first (i.e., when i is not 0), this condition checks if the sorted characters of the current word w are different from the sorted characters of the previous word words[i - 1]. If they are different, the word w is included in the final list.

3. The use of the sorted function on strings is a pivotal step since sorting the characters of a string provides a consistent form to compare whether two words are anagrams. If sorting the two words results in identical strings, then those words are anagrams of each other. The condition sorted(w) != sorted(words[i - 1]) efficiently takes advantage of this.

4. Ultimately, the final list comprises only those words that are not anagrams of the word immediately before them in the array. Consequently, the resulting list is composed of every first word from each potential sequence of anagrams.

5. The list comprehension itself is an efficient way to construct a new list based on the existing words list, avoiding the need for additional storage space which would be required if we were appending to a new list in a loop.

This approach ensures a single-pass solution with a time complexity that is mostly dependent on the sorting of individual words, which is O(n*mlog(m)), where n is the number of words and m is the maximum length of a word in the list.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following array of strings:

1words = ["bat", "tab", "cat"]

Now, let's walk step by step through the algorithm using the solution approach provided:

1. We enumerate through words using a for loop, gaining both the index i and the word w.

2. For the first word, "bat", i is equal to 0. According to our implementation, we should include the first word in the final list because there's no preceding word to compare with. Hence, "bat" is included in the final list.

3. Moving to the second word, "tab", i is now 1. We sort both "tab" and the previous word "bat", resulting in "abt" for both after sorting. Since they are identical after sorting, they are anagrams. According to our condition, "tab" should not appear in the final list because it is an anagram of the previous word. We move on to the next word without including "tab".

4. The next word is "cat", for which i is 2. We sort "cat" to get "act", and we check it against the sorted previous word we included in the final list, which is "bat" sorted to "abt". Since "act" and "abt" are not equal after sorting, "cat" is not an anagram of the previously included word "bat". Therefore, "cat" should be included in the final list.

Using the list comprehension, which runs through these checks for each word, we get the final list which is:

1final_words = ["bat", "cat"]

After going through the whole array, we've successfully filtered out any words that are anagrams of their immediate predecessors, and the resulting array is returned.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code primarily depends on two operations: iterating over the list of words and sorting each word to check if it is an anagram of the previous word.

• Iterating over the list is a O(n) operation, where n is the number of words in the input list.
• For each word, sorting takes O(klogk) time, where k is the average length of a word.

Thus, the total time complexity of the entire operation can be considered O(n * klogk), as for each word in the list, sorting is performed, and then a comparison is made with the sorted previous word, which is a O(k) operation but is negligible relative to the sorting time.

Space Complexity

The space complexity is determined by the additional space required for the sorted words and the space used by the output list.

• Sorting each word creates a new sorted string, resulting in O(k) space for each word (assuming strings are immutable, as in Python). But since this space is reused for each iteration, it is not multiplied by n. Therefore, this does not affect the overall space complexity asymptotically.
• The list comprehension builds a new list, and in the worst case, where no anagrams are removed, this takes O(n) space.

Hence, the space complexity of the code is O(n), accounting for the space needed to store the output list.

Learn more about how to find time and space complexity quickly using problem constraints.