Problem Link - IS IT DSU HARD!!
Problem Statement
You might hear about Disjoint Set Union,click here for more info. Question is, You are given a list of N words (strings containing only lower case English alphabet). Let’s say two words are equivalent if one word can be obtained by rearranging the letters of another word. Your task is, form sets equivalent words and print the size of the largest set.
Approach
To solve this problem, the idea is to group words that are equivalent by using a common representation for all anagrams. For each word, we sort its letters; this sorted version will be the same for any anagrams, allowing us to use it as a “key” in an unordered map. Each unique sorted form in the map represents a distinct group of equivalent words, and the map’s values track the size of each group.
-
Initialize an unordered map
mpwhere each key is the sorted form of a word and each value is the count of words that share this form. -
For each word, sort it to find its “canonical” form, then add or update this form in the map.
-
After processing all words, find the largest value in the map, representing the largest group size of equivalent words.
Time Complexity
O(n \times m \log m), where n is the number of words and m is the maximum length of a word.
Space Complexity
O(n \times m), for storing each word’s sorted version in the hash map.