Uber OA-12 2023

Problem Description

In the modern world of text processing systems, we need to handle words with the same "feeling." Design an algorithm to efficiently group words that share the same "feeling." Two words have the same "feeling" if they contain the same letters with the same frequencies. The output should return word clusters in ascending order, and within each cluster, the words should also be sorted in ascending order.

Input Format:

• An array of words where the length of the array n and the maximum word length m.

Output Format:

• A list of groups of words, where each group consists of words with the same "feeling." The clusters of words and the words within each cluster should be sorted in ascending order.

Constraints:

• The input array can have up to 10^4 words.
• Each word can be up to 100 characters long.
• Ensure the solution has a time complexity of O(n log n) and uses no more than O(n) additional space.

Sample Testcase 1:

Input:

["ate", "listen", "silent", "enlist", "tea", "ate", "eat", "beet", "bet"]

Output:

[["ate", "ate", "eat", "tea"], ["beet"], ["bet"], ["enlist", "listen", "silent"]]

Explanation:

• "ate", "ate", "eat", and "tea" all share the same letters, so they belong to the same group.
• "listen", "silent", and "enlist" all share the same letters and thus form another group.
• "beet" forms a group on its own, and "bet" forms another.