Teaching Kids Programming – Find Maximum Number of String Pairs (Brute Force Algorithm + Hash Set)

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.

Find Maximum Number of String Pairs via Brute Force Algorithm

We can brute force all the pairs in O(C(N, 2)) time, which is O(N^2) quadratic. Then we just have to check if the pairs are reversed of each other. The time complexity is O(MN^2) where M is the length of the string, and in this case, it is 2 character string, thus the overall time complexity is O(N^2). We use O(1) constant space in this algorithm.

1
2
3
4
5
6
7
8
9

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

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

We can use the [::-1] string comprehension to reverse a string, alternatively, we can use the Two Pointer Algorithm.

Find Maximum Number of String Pairs via Hash Set

We can use a Hash Set to remember the strings that we have seen, and then we can improve the time to O(NM) which is O(N) in this case. The space complexity is O(NM) or O(N) in this case.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        seen = set()
        ans = 0
        for i in words:
            if i[::-1] in seen:
                ans += 1
                seen.remove(i[::-1])  # this is optional
            else:
                seen.add(i)
        return ans

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        seen = set()
        ans = 0
        for i in words:
            if i[::-1] in seen:
                ans += 1
                seen.remove(i[::-1])  # this is optional
            else:
                seen.add(i)
        return ans

Since the list does not have duplicates, we can optionally remove the seen string once we have found a pair.

In the next lesson, we will cover another two algorithms (optimal): Teaching Kids Programming – Find Maximum Number of String Pairs (Fixed-size Hash Set and Distinct Groups)

–EOF (The Ultimate Computing & Technology Blog) —