Find Maximum Number of String Pairs

Difficulty: Easy | Acceptance: 82.40% | Paid: No Topics: Array, Hash Table, String, Simulation

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:

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

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

• Examples
• Constraints
• Brute Force
• Hash Set

Examples

Example 1:

Input: words = ["cd","ac","dc","ca","zz"]
Output: 2
Explanation: In this example, we can form 2 pairs of strings:
- We can pair the 0th string "cd" with the 2nd string "dc". The 0th string is the reverse of the 2nd string.
- We can pair the 1st string "ac" with the 3rd string "ca". The 1st string is the reverse of the 3rd string.
It can be shown that we cannot form any more pairs.

Example 2:

Input: words = ["ab","ba","cc"]
Output: 1
Explanation: In this example, we can form 1 pair of strings:
- We can pair the 0th string "ab" with the 1st string "ba". The 0th string is the reverse of the 1st string.
It can be shown that we cannot form any more pairs.

Example 3:

Input: words = ["aa","aa"]
Output: 0
Explanation: In this example, we cannot form any pairs because the strings are not distinct (though the problem statement says distinct, this example highlights the constraint handling if duplicates were present, but strictly per problem constraints, inputs are distinct).

(Note: Based on the problem statement “words consisting of distinct strings”, Example 3 is technically invalid input for the specific constraints of this problem, but illustrates the logic of distinctness.)

Constraints

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

Brute Force

Intuition We can iterate through all possible pairs of strings in the array. For each pair (i, j) where i < j, we check if words[i] is the reverse of words[j]. If it is, we increment our count.

Steps

• Initialize a counter count to 0.
• Use a nested loop to iterate through the array. The outer loop runs from index i = 0 to n-1, and the inner loop runs from index j = i + 1 to n-1.
• Inside the inner loop, check if words[i] is equal to the reverse of words[j].
• If the condition is true, increment count.
• Return count after all iterations.

from typing import List

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

Complexity

• Time: O(n²) where n is the number of strings. We check every pair.
• Space: O(1) as we only use a few variables for counting.
• Notes: Simple to implement but inefficient for very large arrays (though n <= 50 here).

Hash Set

Intuition We can optimize the solution using a hash set. As we iterate through the array, we check if the reverse of the current string has already been seen. If it has, we found a pair. We then remove the matched string from the set to ensure each string is used at most once. If the reverse is not found, we add the current string to the set.

Steps

• Initialize an empty hash set seen and a counter count to 0.
• Iterate through each string w in the array words.
• Calculate the reverse of w, call it rev.
• Check if rev exists in the seen set.
  • If yes, increment count and remove rev from the set (to prevent reusing it).
  • If no, add w to the seen set.
• Return count.

from typing import List

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        seen = set()
        count = 0
        for w in words:
            rev = w[::-1]
            if rev in seen:
                count += 1
                seen.remove(rev)
            else:
                seen.add(w)
        return count

Complexity

• Time: O(n) where n is the number of strings. We iterate through the list once, and set operations are O(1) on average.
• Space: O(n) to store the strings in the set.
• Notes: More efficient than brute force and scales better for larger inputs.