Skip to content

2506. Count Pairs Of Similar Strings 👍

Approach 1: Brute Force

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 (final char c : word.toCharArray())
      mask |= 1 << c - 'a';
    return mask;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def similarPairs(self, words: list[str]) -> int:
    masks = [self._getMask(word) for word in words]
    return sum(masks[i] == masks[j]
               for i, j in itertools.combinations(range(len(masks)), 2))

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

Approach 2: One-Liner

  • Time: $O(n^2)$
  • Space: $O(n)$
1
2
3
4
class Solution:
  def similarPairs(self, words: list[str]) -> int:
    return sum(set(words[i]) == set(words[j])
               for i, j in itertools.combinations(range(len(words)), 2))