# Count Pairs Of Similar Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-pairs-of-similar-strings)
Canonical: https://scaleengineer.com/dsa/problems/count-pairs-of-similar-strings
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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.

# Approaches
## Brute-Force with Helper Function
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use nested loops to iterate through every possible pair of strings `(words[i], words[j])` where `i < j`.
- For each pair, call a helper function `areSimilar(word1, word2)` to check for similarity.
- The `areSimilar` function works as follows:
  - Create a boolean array `set1` of size 26 for `word1`.
  - Iterate through `word1` and mark the characters present by setting the corresponding index in `set1` to `true`.
  - Create a boolean array `set2` of size 26 for `word2` and do the same.
  - Compare `set1` and `set2`. If they are identical, the strings are similar and the function returns `true`.
- If the helper function returns `true`, increment the main `count`.
- After checking all pairs, return `count`.

## Pre-computation of Character Sets
This approach improves upon the brute-force method by avoiding redundant computations. Instead of calculating the character set for each string every time it's part of a comparison, we pre-compute a canonical representation for every string once, store these representations, and then compare them.
**Time:** O(N * L + N^2). The pre-computation step takes O(N * L) time. The comparison step involves O(N^2) pairs, and each comparison of the boolean arrays takes O(1) time (as the size 26 is constant), so this part is O(N^2). · **Space:** O(N). We need to store N boolean arrays, each of size 26. Since 26 is a constant, the complexity is O(N * 26) which simplifies to O(N).
**Pros:** Faster than the pure brute-force approach because character sets are computed only once per string.; Conceptually simple, separating the problem into a processing step and a counting step.
**Cons:** Still has a quadratic time complexity component `O(N^2)` for the comparisons.; Uses more memory than the pure brute-force approach to store the representations.
### Explanation
First, we create an array to store the character set representation for each word. A boolean array of size 26 is a suitable representation. We iterate through the input `words` array once. For each `word`, we compute its character set (the boolean array) and store it in our new array of representations. After this pre-computation step, we use the same nested loop structure as the brute-force approach to iterate through all pairs of indices `(i, j)`. However, instead of comparing the original strings, we now compare their pre-computed boolean arrays. This comparison is much faster than re-generating the sets each time.

```java
import java.util.Arrays;

class Solution {
    public int similarPairs(String[] words) {
        int n = words.length;
        boolean[][] charSets = new boolean[n][26];

        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) {
                charSets[i][c - 'a'] = true;
            }
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Arrays.equals(charSets[i], charSets[j])) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Let `n` be the number of words.
- Create an array of boolean arrays, `charSets`, of size `n x 26`.
- Iterate through the input `words` array from `i = 0` to `n - 1`.
  - For each `words[i]`, compute its character set and store it as a boolean array in `charSets[i]`.
- Initialize a `count` of pairs to 0.
- Use nested loops to iterate through all pairs of indices `(i, j)` where `i < j`.
  - Compare the pre-computed representations `charSets[i]` and `charSets[j]`.
  - If they are identical, increment `count`.
- Return `count`.

## Optimal Approach using Hash Map and Bitmasking
This is the most efficient approach. It avoids the `O(N^2)` pair-wise comparison altogether by using a hash map. We generate a unique, canonical representation for the character set of each string and use the hash map to count how many times each representation appears. This allows us to count the pairs in a single pass.
**Time:** O(N * L), where N is the number of words and L is the average length of a word. We iterate through each word once, and for each word, we iterate through its characters to compute the bitmask. Hash map operations are O(1) on average. · **Space:** O(N) in the worst case, where every word has a unique character set, requiring N entries in the hash map. In the best case (all words are similar), it's O(1).
**Pros:** Most efficient time complexity, linear with respect to the total number of characters.; Scales well for larger N, as it avoids the quadratic comparison loop.
**Cons:** Uses a hash map, which might have slightly more overhead than simple arrays, but is asymptotically superior.
### Explanation
A bitmask is an excellent canonical representation for a character set. Since there are only 26 lowercase English letters, we can use a single integer. The `i`-th bit of the integer is set to 1 if the `i`-th letter of the alphabet is present in the string, and 0 otherwise. We iterate through the `words` array. For each `word`, we compute its bitmask representation. We use a hash map where keys are the bitmasks and values are the counts of strings with that bitmask. As we process each word and compute its mask, we look up the mask in the map. The number of strings we've already seen with the same mask is the number of new pairs the current string forms. We add this number to our total pair count. Then, we increment the count for that mask in the map. This way, we count all pairs in a single pass through the input array.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int similarPairs(String[] words) {
        Map<Integer, Integer> counts = new HashMap<>();
        int pairs = 0;

        for (String word : words) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= (1 << (c - 'a'));
            }
            
            int currentCount = counts.getOrDefault(mask, 0);
            pairs += currentCount;
            counts.put(mask, currentCount + 1);
        }

        return pairs;
    }
}
```
### Algorithm
- Initialize a hash map, `counts`, to store `(bitmask, frequency)`.
- Initialize a `pairs` counter to 0.
- For each `word` in the `words` array:
  - Calculate its bitmask representation. Initialize `mask = 0`. For each character `c` in the word, set the corresponding bit: `mask |= (1 << (c - 'a'))`.
  - Look up the `mask` in the `counts` map to find how many strings with this character set have been seen before. Let this be `currentCount`.
  - The current word forms `currentCount` new pairs. Add this to the total: `pairs += currentCount`.
  - Increment the frequency for this `mask` in the map: `counts.put(mask, currentCount + 1)`.
- After iterating through all words, return `pairs`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int similarPairs(vector<string> &words) {
    int ans = 0;
    unordered_map<int, int> cnt;
    for (auto &w : words) {
      int v = 0;
      for (auto &c : w)
        v |= 1 << c - 'a';
      ans += cnt[v];
      cnt[v]++;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def similarPairs(self, words: List[str]) -> int: ans = 0 cnt = Counter() for w in words: v = 0 for c in w: v |= 1 << (ord(c) - ord("A")) ans += cnt[v] cnt[v] += 1 return ans

```