Count Pairs Of Similar Strings

Difficulty: Easy | Acceptance: 73.70% | Paid: No Topics: Array, Hash Table, String, Bit Manipulation, Counting

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 because they consist of the characters 'a', 'b', and 'c'.
• However, "abacba" and "bcfd" are not similar because they do not consist of the same characters.

Return the number of pairs (i, j) such that i < j and words[i] and words[j] are similar.

• Examples
• Constraints
• Sorting and Hash Map
• Bitmasking

Examples

Input: words = ["aba","aabb","abcd","bac","aabc"]
Output: 2
Explanation: There are 2 pairs that satisfy the conditions:
- (0,1) because both words consist of characters {'a', 'b'}.
- (3,4) because both words consist of characters {'a', 'b', 'c'}.

Input: words = ["aabb","ab","ba"]
Output: 3
Explanation: There are 3 pairs that satisfy the conditions:
- (0,1) because both words consist of characters {'a', 'b'}.
- (0,2) because both words consist of characters {'a', 'b'}.
- (1,2) because both words consist of characters {'a', 'b'}.

Input: words = ["nba","cba","dba"]
Output: 0
Explanation: Since there are no pairs that satisfy the conditions, we return 0.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consist of only lowercase English letters.

Sorting and Hash Map

Intuition Two strings are similar if they contain the exact same set of unique characters. We can normalize each string by extracting its unique characters, sorting them, and joining them back into a key. Strings that are similar will produce the same normalized key. We then count the frequency of each key and calculate the number of pairs possible for each frequency using the combination formula n(n-1)/2.

Steps

• Initialize a hash map to store the frequency of each normalized string key.
• Iterate through each word in the input array.
• For each word, convert it to a set of characters to remove duplicates, then sort the characters and join them to form a unique key.
• Increment the count for this key in the hash map.
• After processing all words, iterate through the values in the hash map.
• For each count v, add v * (v - 1) / 2 to the result.
• Return the result.

from collections import Counter
from typing import List

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        counts = Counter()
        for w in words:
            # Create a sorted string of unique characters
            key = ''.join(sorted(set(w)))
            counts[key] += 1
        
        ans = 0
        for v in counts.values():
            ans += v * (v - 1) // 2
        return ans

Complexity

• Time: O(N * K log K), where N is the number of words and K is the average length of a word. The log K factor comes from sorting the unique characters of each word.
• Space: O(N), to store the frequency map.
• Notes: This approach is intuitive but slightly slower due to the sorting step.

Bitmasking

Intuition Since the input strings consist only of lowercase English letters, we can represent the set of characters in a string using a 26-bit integer (bitmask). Each bit in the integer corresponds to a letter (e.g., bit 0 for ‘a’, bit 1 for ‘b’). Two strings are similar if and only if their bitmasks are identical. This allows for very efficient comparison and counting using bitwise operations.

Steps

• Initialize a hash map to store the frequency of each bitmask.
• Iterate through each word in the input array.
• For each word, initialize a mask to 0.
• Iterate through each character in the word.
• Calculate the bit position: charCode - 'a'.
• Set the corresponding bit in the mask using bitwise OR: mask |= (1 << bitPosition).
• Increment the count for this mask in the hash map.
• After processing all words, iterate through the values in the hash map.
• For each count v, add v * (v - 1) / 2 to the result.
• Return the result.

from collections import Counter
from typing import List

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        counts = Counter()
        for w in words:
            mask = 0
            for c in w:
                mask |= 1 << (ord(c) - ord('a'))
            counts[mask] += 1
        
        ans = 0
        for v in counts.values():
            ans += v * (v - 1) // 2
        return ans

Complexity

• Time: O(N * K), where N is the number of words and K is the average length of a word. We iterate through every character once.
• Space: O(N), to store the frequency map.
• Notes: This is the optimal approach for this problem, avoiding the overhead of sorting and string manipulation.