2744

2744. Find Maximum Number of String Pairs (Easy)

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.

Related Topics:
Array, Hash Table, String, Simulation

Similar Questions:

• Group Shifted Strings (Medium)
• Palindrome Pairs (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/find-maximum-number-of-string-pairs
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& A) {
        unordered_set<string> s;
        int ans = 0;
        for (auto &w : A) {
            string r(rbegin(w), rend(w));
            if (s.count(r)) ++ans;
            s.insert(w);
        }
        return ans;
    }
};