Detect anagram in array

Question

Given an array of strings, write a function to detect and return all pairs of strings that are anagrams of each other. The function should take the array as input and output a list of tuples, where each tuple contains two anagram strings.

Codemia · Accepted Answer

To detect anagrams in an array of strings, we need to identify pairs of strings that have the same character frequencies. The best approach here is to use a hash map (dictionary in Python) to group strings that are anagrams of each other. By sorting each string or creating a frequency count of characters, we can uniquely identify anagrams. This approach leverages the concept of frequency counting, which is efficient for this type of problem.

1. Initialize an empty dictionary to hold lists of anagram groups.
2. Iterate through each string in the input array:
   - For each string, sort the characters and use the sorted string as a key in the dictionary.
   - Append the original string to the list corresponding to this key.
3. After processing all strings, filter the dictionary to include only those keys that have more than one associated string (indicating that there are anagrams).
4. Generate pairs of strings for each group of anagrams.

For example, given the input `['eat', 'tea', 'tan', 'ate', 'nat', 'bat']`, the sorted keys would be {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}. The output pairs would then be `('eat', 'tea')`, `('eat', 'ate')`, `('tea', 'ate')`, `('tan', 'nat')`.

Here is the Python solution implementing the above approach:

```python
from collections import defaultdict

def detect_anagrams(strings):
    anagram_map = defaultdict(list)

for string in strings:
        # Sort the string to create a key
        sorted_str = ''.join(sorted(string))
        # Append the original string to the anagram group
        anagram_map[sorted_str].append(string)

result = []
    # Generate pairs from the anagram groups
    for group in anagram_map.values():
        if len(group) > 1:
            for i in range(len(group)):
                for j in range(i + 1, len(group)):
                    result.append((group[i], group[j]))

return result
```

The time complexity of this solution is O(n * k log k), where n is the number of strings and k is the maximum length of a string. This accounts for sorting each string. The space complexity is O(n) for storing the anagram groups in the dictionary. Given the constraints, this approach is efficient since it processes each string only a few times.

1. If the input array is empty, the output should be an empty list `[]`.
2. If there is only one string in the array, the output should also be `[]` since there can't be an anagram pair.
3. Strings that are not anagrams but are identical (e.g., `['test', 'test']`) should still result in pairs (e.g., `('test', 'test')`).
4. If all strings are unique and no anagrams exist, the output should be an empty list.

Detect anagram in array

Cloudflare

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Cloudflare Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string