Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2506.html

2506. Count Pairs Of Similar Strings

Description

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.

Solutions

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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
    
    
  • func similarPairs(words []string) (ans int) {
    	cnt := map[int]int{}
    	for _, w := range words {
    		v := 0
    		for _, c := range w {
    			v |= 1 << (c - 'a')
    		}
    		ans += cnt[v]
    		cnt[v]++
    	}
    	return
    }
    
  • use std::collections::HashMap;
    
    impl Solution {
        pub fn similar_pairs(words: Vec<String>) -> i32 {
            let mut ans = 0;
            let mut hash: HashMap<i32, i32> = HashMap::new();
    
            for w in words {
                let mut v = 0;
    
                for c in w.chars() {
                    v |= (1 << (c as u8 - b'a'))
                }
    
                ans += hash.get(&v).unwrap_or(&0);
                *hash.entry(v).or_insert(0) += 1;
            }
    
            ans
        }
    }
    
  • function similarPairs(words: string[]): number {
        let ans = 0;
        const cnt: Map<number, number> = new Map();
        for (const w of words) {
            let v = 0;
            for (let i = 0; i < w.length; ++i) {
                v |= 1 << (w.charCodeAt(i) - 'a'.charCodeAt(0));
            }
            ans += cnt.get(v) || 0;
            cnt.set(v, (cnt.get(v) || 0) + 1);
        }
        return ans;
    }
    
    

All Problems

All Solutions