We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Pairs Of Similar Strings

Difficulty: Easy

Problem Description

You are given a 0-indexed string array words. Two strings are similar if they 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.

Key Insights

  • Two strings are similar if they contain the same unique characters, regardless of their order or frequency.
  • A set can be used to represent the unique characters of each string.
  • The problem can be solved using a hash map to count how many strings share the same set of unique characters.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of strings and m is the maximum length of a string (since we need to process each character of each string).

Space Complexity: O(n), where n is the number of unique character sets.

Solution

To solve the problem, we will use a hash map to store the unique character sets of each string. The approach involves the following steps:

  1. For each string in the input array, convert it into a set of characters.
  2. Use the frozenset data structure to ensure that the character sets can be used as keys in the hash map.
  3. Count the frequency of each unique character set in the hash map.
  4. For each unique character set that appears k times, the number of pairs that can be formed is given by the combination formula C(k, 2) = k * (k - 1) / 2.
  5. Sum these counts to get the final answer.

Code Solutions

def countSimilarPairs(words):
    from collections import defaultdict
    
    # Dictionary to count occurrences of unique character sets
    char_set_count = defaultdict(int)

    for word in words:
        # Create a frozenset of characters in the word
        char_set = frozenset(word)
        char_set_count[char_set] += 1

    # Calculate the number of similar pairs
    result = 0
    for count in char_set_count.values():
        if count > 1:
            result += count * (count - 1) // 2

    return result

# Example usage:
words = ["aba","aabb","abcd","bac","aabc"]
print(countSimilarPairs(words))  # Output: 2
← Back to All Questions