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.
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; }}Video 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.