Teaching Kids Programming – Count Pairs Of Similar Strings (Bruterforce, Hash Map / Counter and Bit masking)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Hints:
How can you check if two strings are similar?
Use a hashSet to store the character of each string.

Count Pairs Of Similar Strings (Bruteforce Algorithm)

We can bruteforce every pairs in O(N^2) time i.e. C(N, 2) picking two out of N which results in N(N-1)/2 pairs. Then, we check if two strings are similar by checking the equality of the sets. The time complexity is O(N*N*M) where N is the length of the array/strings, and the M is the average length of each word. The space complexity is O(M) because of converting string to a set for comparision.

1
2
3
4
5
6
7
8
9

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        ans = 0
        n = len(words)
        for i in range(n):
            for j in range(i):
                if set(words[i]) == set(words[j]):
                    ans += 1
        return ans    

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        ans = 0
        n = len(words)
        for i in range(n):
            for j in range(i):
                if set(words[i]) == set(words[j]):
                    ans += 1
        return ans    

Count Pairs Of Similar Strings (Hash Map and Counter)

We can record the number of the same “similar” strings in a Counter aka Hash Map, and then when we meet a new “same” similar string, we accumulate the number of new pairs. We can convert each string to a set, and sort it, join them to a string, which uniquely identifies the similarity.

1
2
3
4
5
6
7
8
9

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        d = Counter()
        ans = 0
        for w in words:
            x = "".join(sorted(set(w)))
            ans += d[x]
            d[x] += 1            
        return ans

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        d = Counter()
        ans = 0
        for w in words:
            x = "".join(sorted(set(w)))
            ans += d[x]
            d[x] += 1            
        return ans

The time complexity is O(N*M*LogM) and the space complexity is O(NM). N is the number of the given strings. M is the average length of a word.

Count Pairs Of Similar Strings (Bit masking)

All the given strings are lowercase, and thus we can convert a string to a big integer. We obtain the ASCII code of the characters, and then mask the corresponding bits in the integer. The ‘a’ corresponds to ‘1’, ‘b’ corresponds to ’10’, ‘c’ corresponds to ‘100’ and so on.

The time complexity is O(NM) and the space complexity is O(M).

1
2
3
4
5
6
7
8
9

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        d = Counter()
        ans = 0
        for w in words:
            x = reduce(or_, (1 << ord(ch) - 97 for ch in w))
            ans += d[x]
            d[x] += 1            
        return ans

class Solution:
    def similarPairs(self, words: List[str]) -> int:
        d = Counter()
        ans = 0
        for w in words:
            x = reduce(or_, (1 << ord(ch) - 97 for ch in w))
            ans += d[x]
            d[x] += 1            
        return ans

We use the “reduce” function here to compute the masking value for each string, and it can be written as the following traditional method.

1
2
3

x = 0
for ch in w:
    x |= 1 << ord(ch) - 97;

x = 0
for ch in w:
    x |= 1 << ord(ch) - 97;

The reduce function applies the first parameter (which is a function and can be lambda function) to the iterator/list (second parameter).

–EOF (The Ultimate Computing & Technology Blog) —