2506. Count Pairs Of Similar Strings LeetCode Solution

In this guide, you will get 2506. Count Pairs Of Similar Strings LeetCode Solution with the best time and space complexity. The solution to Count Pairs Of Similar Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Pairs Of Similar Strings solution in C++
Count Pairs Of Similar Strings solution in Java
Count Pairs Of Similar Strings solution in Python
Additional Resources

2506. Count Pairs Of Similar Strings LeetCode Solution image

Problem Statement of Count Pairs Of Similar Strings

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 <= 100
1 <= words[i].length <= 100
words[i] consist of only lowercase English letters.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

2506. Count Pairs Of Similar Strings LeetCode Solution in C++

class Solution {
 public:
  int similarPairs(vector<string>& words) {
    int ans = 0;
    vector<int> masks;

    for (const string& word : words)
      masks.push_back(getMask(word));

    for (int i = 0; i < masks.size(); ++i)
      for (int j = i + 1; j < masks.size(); ++j)
        if (masks[i] == masks[j])
          ++ans;

    return ans;
  }

 private:
  int getMask(const string& word) {
    int mask = 0;
    for (const char c : word)
      mask |= 1 << c - 'a';
    return mask;
  }
};
/* code provided by PROGIEZ */

2506. Count Pairs Of Similar Strings LeetCode Solution in Java

class Solution {
  public int similarPairs(String[] words) {
    int ans = 0;
    int[] masks = new int[words.length];

    for (int i = 0; i < words.length; ++i)
      masks[i] = getMask(words[i]);

    for (int i = 0; i < masks.length; ++i)
      for (int j = i + 1; j < masks.length; ++j)
        if (masks[i] == masks[j])
          ++ans;

    return ans;
  }

  private int getMask(final String word) {
    int mask = 0;
    for (const char c : word.toCharArray())
      mask |= 1 << c - 'a';
    return mask;
  }
}
// code provided by PROGIEZ

2506. Count Pairs Of Similar Strings LeetCode Solution in Python

class Solution:
  def similarPairs(self, words: list[str]) -> int:
    ans = 0

    def getMask(word: str) -> int:
      mask = 0
      for c in word:
        mask |= 1 << ord(c) - ord('a')
      return mask

    masks = [getMask(word) for word in words]

    for i in range(len(masks)):
      for j in range(i + 1, len(masks)):
        if masks[i] == masks[j]:
          ans += 1

    return ans
 # code by PROGIEZ