You are given a 0-indexed string array words.
Two strings are similar if they consist of the same characters.
"abca" and "cba" are similar since both consist of characters 'a', 'b', and 'c'."abacba" and "bcfd" are not similar since they do not consist of the same characters.Return the number of pairs (i, j) such that 0 <= i < j <= word.length - 1 and the two strings words[i] and words[j] are similar.
Example 1:
Input: words = ["aba","aabb","abcd","bac","aabc"] Output: 2 Explanation: There are 2 pairs that satisfy the conditions: - i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. - i = 3 and j = 4 : both words[3] and words[4] only consist of characters 'a', 'b', and 'c'.
Example 2:
Input: words = ["aabb","ab","ba"] Output: 3 Explanation: There are 3 pairs that satisfy the conditions: - i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. - i = 0 and j = 2 : both words[0] and words[2] only consist of characters 'a' and 'b'. - i = 1 and j = 2 : both words[1] and words[2] only consist of characters 'a' and 'b'.
Example 3:
Input: words = ["nba","cba","dba"] Output: 0 Explanation: Since there does not exist any pair that satisfies the conditions, we return 0.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 100words[i] consist of only lowercase English letters.Problem Overview: You receive an array of strings. Two strings are considered similar if they contain exactly the same set of characters, regardless of order or frequency. The task is to count how many pairs (i, j) exist such that both strings share the identical character set.
Approach 1: Set Reduction Approach (O(n² * k) time, O(k) space)
Reduce each string to a set of unique characters, then compare every pair of strings. Two strings are similar if their character sets are equal. Iterate through all pairs using nested loops and perform a set comparison for each pair. If the sets match, increment the pair count. This approach is straightforward and easy to implement using string processing and basic array traversal.
The downside is the quadratic pair comparison. For n strings and average length k, building the sets costs O(k) and comparing pairs pushes the total runtime to O(n² * k). Space usage remains O(k) per temporary set. This works fine for small inputs but becomes inefficient when the number of strings grows.
Approach 2: Hash Map Character Signature (O(n * k) time, O(n) space)
A more scalable solution converts each string into a canonical character signature and groups identical signatures using a hash map. The most efficient signature uses a 26‑bit integer mask where each bit represents whether a letter appears in the string. Iterate through the characters and set the corresponding bit using bitwise OR. Strings with the same character set produce identical masks.
Store frequencies of these masks in a hash table. Each time a mask appears again, it forms pairs with all previous strings that had the same mask. If a signature appears f times, it contributes f * (f - 1) / 2 pairs. Building each mask takes O(k), and processing all strings costs O(n * k) time with O(n) additional storage. The bitmask technique leverages bit manipulation to create a compact and fast signature.
Recommended for interviews: Interviewers typically expect the hash map signature approach. The brute-force pair comparison demonstrates understanding of the similarity definition, but the optimized solution shows you can reduce repeated comparisons by hashing canonical representations. Recognizing that only the character set matters, not frequency or order, leads directly to the bitmask optimization.
This approach involves converting each word into a set of characters. If two words have the same set of characters, they are similar. Convert the string into a set of characters and compare these sets to identify similar words.
We first convert each word in the list into a set of unique characters. We then compare each pair of sets to see if they are equal. If they are, the words are similar, and we increase our count.
Python
JavaScript
Time Complexity: O(n^2 * m) where n is the number of words and m is the average length of words due to set comparisons.
Space Complexity: O(nm) for storing the sets of characters.
This approach involves creating a 'signature' for each word using a hashable descriptor such as sorted unique characters. Use a hashmap to count these signatures, and calculate the number of pairs from these counts.
This Java solution uses a HashMap to track the frequency of each sorted character string (signature). Each pair of matching signatures contributes to the count according to combinations formula nC2 = n*(n-1)/2.
Time Complexity: O(n * m log m) due to sorting.
Space Complexity: O(n) because of the hashmap to store counts.
For each string, we can convert it into a binary number of length 26, where the i-th bit being 1 indicates that the string contains the i-th letter.
If two strings contain the same letters, their binary numbers are the same. Therefore, for each string, we use a hash table to count the occurrences of its binary number. Each time we add the count to the answer, then increment the count of its binary number by 1.
The time complexity is O(L), and the space complexity is O(n). Here, L is the total length of all strings, and n is the number of strings.
| Approach | Complexity |
|---|---|
| Set Reduction Approach | Time Complexity: O(n^2 * m) where n is the number of words and m is the average length of words due to set comparisons. |
| Hash Map Character Signature Approach | Time Complexity: O(n * m log m) due to sorting. |
| Hash Table + Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set Reduction Pair Comparison | O(n² * k) | O(k) | Small input sizes or when implementing a quick brute-force check |
| Hash Map Character Signature (Bitmask) | O(n * k) | O(n) | General case and interview settings where efficient grouping is required |
2506. Count Pairs Of Similar Strings | Weekly Contest 324 | LeetCode 2506 • Bro Coders • 2,634 views views
Watch 9 more video solutions →Practice Count Pairs Of Similar Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor