Two strings are said to be similar if they are composed of the same characters.
For example, "abaca" and "cba" are similar since both of them are composed of characters 'a', 'b', and 'c'. However, "abaca" and "bcd" are not similar since they do not share all of the same letters.
Given an array of strings words of length n, find the number of pairs of strings that are similar.
Note:
- Each string is composed of lowercase English characters only.
- Pairs are considered index-wise, i.e., two equal strings at different indices are counted as separate pairs.
- A pair at indices
(i, j)is the same as the pair at(j, i).
Example
Consider n = 3, words = ["xyz", "foo", "of"].
Here, the strings "foo" and "of" are similar because they are composed of the same characters ['o', 'f']. There are no other similar pairs, so the answer is 1.
Function Description
Complete the function countSimilarPairs in the editor below.
countSimilarPairs has the following parameter:
string words[n]: an array ofnstrings
Returns
long int: the number of similar pairs
The key idea is to normalize each word into a signature that represents its set of distinct lowercase letters. Two words are similar if and only if their signatures are identical. Since the alphabet is fixed, a 26-bit bitmask is an efficient choice: build one mask per word, count how many times each mask appears, and sum combinations of identical masks using C(cnt, 2). This handles duplicate words at different indices correctly and runs efficiently under the given input limits.
