Count Pairs Of Similar Strings
EasyPrompt
You are given a 0-indexed string array words.
Two strings are similar if they consist of the same characters.
- For example,
"abca"and"cba"are similar since both consist of characters'a','b', and'c'. - However,
"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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It iterates through every possible pair of strings (words[i], words[j]) where i < j and checks if they are similar using a helper function. This is the most straightforward but least efficient method.
Algorithm
- Initialize a counter
countto 0. - Use nested loops to iterate through every possible pair of strings
(words[i], words[j])wherei < j. - For each pair, call a helper function
areSimilar(word1, word2)to check for similarity. - The
areSimilarfunction works as follows:- Create a boolean array
set1of size 26 forword1. - Iterate through
word1and mark the characters present by setting the corresponding index inset1totrue. - Create a boolean array
set2of size 26 forword2and do the same. - Compare
set1andset2. If they are identical, the strings are similar and the function returnstrue.
- Create a boolean array
- If the helper function returns
true, increment the maincount. - After checking all pairs, return
count.
Walkthrough
A helper function, areSimilar(word1, word2), is used to determine similarity. Inside the helper function, we determine the set of unique characters for each word. A simple way to do this is by using a boolean array of size 26, where each index corresponds to a letter of the alphabet. We create one boolean array for word1 and another for word2. We iterate through each word, marking the corresponding letters as true in their respective arrays. Finally, we compare the two boolean arrays. If they are identical, the strings are similar. The main function uses nested loops to generate all pairs (i, j) and calls the helper function. A counter is incremented for each similar pair found.
class Solution { public int similarPairs(String[] words) { int count = 0; int n = words.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (areSimilar(words[i], words[j])) { count++; } } } return count; } private boolean areSimilar(String word1, String word2) { boolean[] set1 = new boolean[26]; for (char c : word1.toCharArray()) { set1[c - 'a'] = true; } boolean[] set2 = new boolean[26]; for (char c : word2.toCharArray()) { set2[c - 'a'] = true; } for (int i = 0; i < 26; i++) { if (set1[i] != set2[i]) { return false; } } return true; }}Complexity
Time
O(N^2 * L), where N is the number of words and L is the maximum length of a word. The nested loops run in O(N^2), and for each pair, the `areSimilar` function takes O(L) time to build the character sets and O(1) to compare them.
Space
O(1). The space used by the boolean arrays in the helper function is constant because the alphabet size is fixed at 26. No other significant space is used.
Trade-offs
Pros
Simple to understand and implement.
Very low memory usage as it only requires constant extra space for the helper function.
Cons
Inefficient due to its
O(N^2 * L)time complexity.The character set for each string is re-calculated multiple times, leading to redundant work.
This approach improves upon the brute-force method by avoiding redundant computations. Instead of calculating the character set for each string every time it's part of a comparison, we pre-compute a canonical representation for every string once, store these representations, and then compare them.
Algorithm
- Let
nbe the number of words. - Create an array of boolean arrays,
charSets, of sizen x 26. - Iterate through the input
wordsarray fromi = 0ton - 1.- For each
words[i], compute its character set and store it as a boolean array incharSets[i].
- For each
- Initialize a
countof pairs to 0. - Use nested loops to iterate through all pairs of indices
(i, j)wherei < j.- Compare the pre-computed representations
charSets[i]andcharSets[j]. - If they are identical, increment
count.
- Compare the pre-computed representations
- Return
count.
Walkthrough
First, we create an array to store the character set representation for each word. A boolean array of size 26 is a suitable representation. We iterate through the input words array once. For each word, we compute its character set (the boolean array) and store it in our new array of representations. After this pre-computation step, we use the same nested loop structure as the brute-force approach to iterate through all pairs of indices (i, j). However, instead of comparing the original strings, we now compare their pre-computed boolean arrays. This comparison is much faster than re-generating the sets each time.
import java.util.Arrays; class Solution { public int similarPairs(String[] words) { int n = words.length; boolean[][] charSets = new boolean[n][26]; for (int i = 0; i < n; i++) { for (char c : words[i].toCharArray()) { charSets[i][c - 'a'] = true; } } int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (Arrays.equals(charSets[i], charSets[j])) { count++; } } } return count; }}Complexity
Time
O(N * L + N^2). The pre-computation step takes O(N * L) time. The comparison step involves O(N^2) pairs, and each comparison of the boolean arrays takes O(1) time (as the size 26 is constant), so this part is O(N^2).
Space
O(N). We need to store N boolean arrays, each of size 26. Since 26 is a constant, the complexity is O(N * 26) which simplifies to O(N).
Trade-offs
Pros
Faster than the pure brute-force approach because character sets are computed only once per string.
Conceptually simple, separating the problem into a processing step and a counting step.
Cons
Still has a quadratic time complexity component
O(N^2)for the comparisons.Uses more memory than the pure brute-force approach to store the representations.
This is the most efficient approach. It avoids the O(N^2) pair-wise comparison altogether by using a hash map. We generate a unique, canonical representation for the character set of each string and use the hash map to count how many times each representation appears. This allows us to count the pairs in a single pass.
Algorithm
- Initialize a hash map,
counts, to store(bitmask, frequency). - Initialize a
pairscounter to 0. - For each
wordin thewordsarray:- Calculate its bitmask representation. Initialize
mask = 0. For each charactercin the word, set the corresponding bit:mask |= (1 << (c - 'a')). - Look up the
maskin thecountsmap to find how many strings with this character set have been seen before. Let this becurrentCount. - The current word forms
currentCountnew pairs. Add this to the total:pairs += currentCount. - Increment the frequency for this
maskin the map:counts.put(mask, currentCount + 1).
- Calculate its bitmask representation. Initialize
- After iterating through all words, return
pairs.
Walkthrough
A bitmask is an excellent canonical representation for a character set. Since there are only 26 lowercase English letters, we can use a single integer. The i-th bit of the integer is set to 1 if the i-th letter of the alphabet is present in the string, and 0 otherwise. We iterate through the words array. For each word, we compute its bitmask representation. We use a hash map where keys are the bitmasks and values are the counts of strings with that bitmask. As we process each word and compute its mask, we look up the mask in the map. The number of strings we've already seen with the same mask is the number of new pairs the current string forms. We add this number to our total pair count. Then, we increment the count for that mask in the map. This way, we count all pairs in a single pass through the input array.
import java.util.HashMap;import java.util.Map; class Solution { public int similarPairs(String[] words) { Map<Integer, Integer> counts = new HashMap<>(); int pairs = 0; for (String word : words) { int mask = 0; for (char c : word.toCharArray()) { mask |= (1 << (c - 'a')); } int currentCount = counts.getOrDefault(mask, 0); pairs += currentCount; counts.put(mask, currentCount + 1); } return pairs; }}Complexity
Time
O(N * L), where N is the number of words and L is the average length of a word. We iterate through each word once, and for each word, we iterate through its characters to compute the bitmask. Hash map operations are O(1) on average.
Space
O(N) in the worst case, where every word has a unique character set, requiring N entries in the hash map. In the best case (all words are similar), it's O(1).
Trade-offs
Pros
Most efficient time complexity, linear with respect to the total number of characters.
Scales well for larger N, as it avoids the quadratic comparison loop.
Cons
Uses a hash map, which might have slightly more overhead than simple arrays, but is asymptotically superior.
Solutions
Solution
class Solution {public int similarPairs(String[] words) { int ans = 0; Map<Integer, Integer> cnt = new HashMap<>(); for (var w : words) { int v = 0; for (int i = 0; i < w.length(); ++i) { v |= 1 << (w.charAt(i) - 'a'); } ans += cnt.getOrDefault(v, 0); cnt.put(v, cnt.getOrDefault(v, 0) + 1); } return ans; }}class Solution {public: int similarPairs(vector<string> &words) { int ans = 0; unordered_map<int, int> cnt; for (auto &w : words) { int v = 0; for (auto &c : w) v |= 1 << c - 'a'; ans += cnt[v]; cnt[v]++; } return ans; }};class Solution: def similarPairs(self, words: List[str]) -> int: ans = 0 cnt = Counter() for w in words: v = 0 for c in w: v |= 1 << (ord(c) - ord("A")) ans += cnt[v] cnt[v] += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.