Find Maximum Number of String Pairs

Problem Description

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.

Key Insights

• Each string has a unique reverse that may match with another string in the array.
• Since the strings are distinct, we can use a hash set to track pairs as we identify them.
• The problem can be approached by iterating through the list and checking for the existence of the reversed string.

Space and Time Complexity

Time Complexity: O(n), where n is the number of strings in the array, since we will check each string once. Space Complexity: O(n), for storing the reversed strings in a hash set.

Solution

The solution involves using a hash set to store the strings and checking if the reversed version of each string exists in that set. If it does, we form a pair and remove both strings from further consideration to ensure each string is used at most once.

1. Initialize a hash set to keep track of the strings.
2. Initialize a variable to count pairs.
3. Iterate through each string in the array:
   • Reverse the string and check if it exists in the set.
   • If it exists, increase the pair count and remove both the original and reversed strings from the set.
4. Return the total count of pairs.

Code Solutions