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 that0 <= i < j <= word.length - 1 and the two stringswords[i]andwords[j]are similar.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5
6

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

1
2
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.

Solution

Method 1 – Bitmasking and Hash Map

Intuition

Two strings are similar if they have the same set of characters. We can represent the set of characters in a string as a bitmask of 26 bits (one for each lowercase letter). Strings with the same bitmask are similar.

Approach

  1. For each word, compute a bitmask representing the set of characters in the word.
  2. Use a hash map to count the frequency of each bitmask.
  3. For each bitmask with count c, the number of pairs is c * (c - 1) // 2.
  4. Sum up the pairs for all bitmasks.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int similarPairs(vector<string>& words) {
        unordered_map<int, int> mp;
        for (auto& w : words) {
            int mask = 0;
            for (char ch : w) mask |= 1 << (ch - 'a');
            mp[mask]++;
        }
        int ans = 0;
        for (auto& [_, c] : mp) ans += c * (c - 1) / 2;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func similarPairs(words []string) int {
    mp := map[int]int{}
    for _, w := range words {
        mask := 0
        for _, ch := range w {
            mask |= 1 << (ch - 'a')
        }
        mp[mask]++
    }
    ans := 0
    for _, c := range mp {
        ans += c * (c - 1) / 2
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int similarPairs(String[] words) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (String w : words) {
            int mask = 0;
            for (char ch : w.toCharArray()) mask |= 1 << (ch - 'a');
            mp.put(mask, mp.getOrDefault(mask, 0) + 1);
        }
        int ans = 0;
        for (int c : mp.values()) ans += c * (c - 1) / 2;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun similarPairs(words: Array<String>): Int {
        val mp = mutableMapOf<Int, Int>()
        for (w in words) {
            var mask = 0
            for (ch in w) mask = mask or (1 shl (ch - 'a'))
            mp[mask] = mp.getOrDefault(mask, 0) + 1
        }
        var ans = 0
        for (c in mp.values) ans += c * (c - 1) / 2
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def similarPairs(self, words: list[str]) -> int:
        from collections import Counter
        mp = Counter()
        for w in words:
            mask = 0
            for ch in w:
                mask |= 1 << (ord(ch) - ord('a'))
            mp[mask] += 1
        ans = 0
        for c in mp.values():
            ans += c * (c - 1) // 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn similar_pairs(words: Vec<String>) -> i32 {
        use std::collections::HashMap;
        let mut mp = HashMap::new();
        for w in &words {
            let mut mask = 0;
            for ch in w.chars() {
                mask |= 1 << (ch as u8 - b'a');
            }
            *mp.entry(mask).or_insert(0) += 1;
        }
        let mut ans = 0;
        for &c in mp.values() {
            ans += c * (c - 1) / 2;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    similarPairs(words: string[]): number {
        const mp: Record<number, number> = {};
        for (const w of words) {
            let mask = 0;
            for (const ch of w) mask |= 1 << (ch.charCodeAt(0) - 97);
            mp[mask] = (mp[mask] || 0) + 1;
        }
        let ans = 0;
        for (const c of Object.values(mp)) ans += c * (c - 1) / 2;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * L) where n is the number of words and L is the average length of a word (for bitmask computation).
  • 🧺 Space complexity: O(n) for the hash map storing bitmasks.