Teaching Kids Programming – Find Maximum Number of String Pairs (Fixed-size Hash Set and Distinct Groups)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a 0-indexed array words consisting of distinct strings. The string words[i] can be paired with the string words[j] if:

• The string words[i] is equal to the reversed string of words[j].
• 0 <= i < j < words.length.

Return the maximum number of pairs that can be formed from the array words. Note that each string can belong in at most one pair.

Example 1:
Input: words = [“cd”,”ac”,”dc”,”ca”,”zz”]
Output: 2
Explanation: In this example, we can form 2 pair of strings in the following way:
– We pair the 0th string with the 2nd string, as the reversed string of word[0] is “dc” and is equal to words[2].
– We pair the 1st string with the 3rd string, as the reversed string of word[1] is “ca” and is equal to words[3].
It can be proven that 2 is the maximum number of pairs that can be formed.

Example 2:
Input: words = [“ab”,”ba”,”cc”]
Output: 1
Explanation: In this example, we can form 1 pair of strings in the following way:
– We pair the 0th string with the 1st string, as the reversed string of words[1] is “ab” and is equal to words[0].
It can be proven that 1 is the maximum number of pairs that can be formed.

Example 3:
Input: words = [“aa”,”ab”]
Output: 0
Explanation: In this example, we are unable to form any pair of strings.

Constraints:

• 1 <= words.length <= 50
• words[i].length == 2
• words consists of distinct strings.
• words[i] contains only lowercase English letters.

Last lesson, we talked about the same problem but using the Bruteforce Algorithm and the Hash Set: Teaching Kids Programming – Find Maximum Number of String Pairs (Brute Force Algorithm + Hash Set). Today, we introduce another two algorithms.

Find Maximum Number of String Pairs (Fixed-size Hash Set)

Since the given strings in the list are 2-characters only, therefore, there are 676 possibilities, so we can use a fixed size buckets/arrays instead of a hash set. And we can map a two-character string to the location of its bucket using the ord (ASCII) function e.g. the first ASCII code multiplied 26 plus the second ASCII code.

1
2
3
4
5
6
7
8
9

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        ## two character - 676 buckets
        seen = [False] * (26*26)
        ans = 0
        for i in words:
            ans += seen[(ord(i[0])- 97) * 26 + ord(i[1]) - 97]
            seen[(ord(i[1]) - 97) * 26 + ord(i[0]) - 97] = True
        return ans

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        ## two character - 676 buckets
        seen = [False] * (26*26)
        ans = 0
        for i in words:
            ans += seen[(ord(i[0])- 97) * 26 + ord(i[1]) - 97]
            seen[(ord(i[1]) - 97) * 26 + ord(i[0]) - 97] = True
        return ans

The time is O(N) and the space is O(1) as we are allocating a fixed-size array which is basically O(1) constant.

Find Maximum Number of String Pairs (Distinct Groups)

Another solution is based on the fact that the array does not have a duplicate string, and also a string can only be paired up with another string at most once. Thus we can find out the number of distinct groups (by using the frozen set on each string), and the answer is N-G where N is the total number of strings in the array (which is given) and G is the number of the distinct groups.

We can’t perform a set on another set since this (a set) is unhashable, but a frozen set is fine, since frozen is immutable which is just like a constant.

1
2
3

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        return len((words)) - len(frozenset([frozenset(w) for w in words]))

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        return len((words)) - len(frozenset([frozenset(w) for w in words]))

–EOF (The Ultimate Computing & Technology Blog) —