# Find Maximum Number of String Pairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-maximum-number-of-string-pairs)
Canonical: https://scaleengineer.com/dsa/problems/find-maximum-number-of-string-pairs
**Data structures:** Array, Hash Table, String
---
## Problem
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.

# Approaches
## Brute-Force with Nested Loops
This approach iterates through all possible pairs of strings in the array and checks if they form a valid pair. A pair is valid if one string is the reverse of the other. To ensure each string is part of at most one pair, we use a boolean array to mark strings that have already been matched.
**Time:** O(N^2), where N is the number of strings in `words`. The nested loops dominate the runtime. The operations inside the loop (character access and comparison) are constant time since the string length is fixed at 2. · **Space:** O(N), where N is the number of strings in `words`. This is for the `used` boolean array.
**Pros:** Simple and intuitive to understand.; Does not require complex data structures.; Low space overhead.
**Cons:** Inefficient for large inputs due to the quadratic time complexity. While acceptable for the given constraints (N <= 50), it does not scale well.
### Explanation
We can solve this problem by systematically comparing every string with every other string that comes after it in the array.

We initialize a counter for the number of pairs to zero. To avoid pairing a string more than once, we use a boolean array, `used`, to keep track of which strings have already been included in a pair.

We use a nested loop. The outer loop iterates from `i = 0` to `n-1` (where `n` is the number of words), and the inner loop iterates from `j = i + 1` to `n-1`. This structure ensures we only consider pairs `(words[i], words[j])` where `i < j`.

Inside the loops, if both `words[i]` and `words[j]` have not been used yet, we check if `words[i]` is the reverse of `words[j]`. Since each string has a length of 2, reversing `words[i]` (e.g., "ab") is straightforward: we swap its two characters to get the reversed string (e.g., "ba").

If `words[j]` matches the reversed `words[i]`, we've found a pair. We increment our pair counter and mark both `words[i]` and `words[j]` as used by setting `used[i]` and `used[j]` to `true`. We then break the inner loop for the current `i` because `words[i]` has found its unique partner.

After checking all possible pairs, the value of the counter is the maximum number of pairs.

```java
class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int n = words.length;
        int count = 0;
        boolean[] used = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                if (used[j]) {
                    continue;
                }
                String s1 = words[i];
                String s2 = words[j];
                // Since length is 2, reversing is just swapping characters.
                if (s1.charAt(0) == s2.charAt(1) && s1.charAt(1) == s2.charAt(0)) {
                    count++;
                    used[i] = true;
                    used[j] = true;
                    break; // words[i] is now paired, move to the next i
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `pairs` to 0.
*   Create a boolean array `used` of the same size as `words`, initialized to `false`. This will track which strings have already been paired.
*   Use a nested loop to iterate through all pairs of indices `(i, j)` such that `0 <= i < j < words.length`.
*   In the outer loop, if `used[i]` is `true`, skip to the next `i`.
*   In the inner loop, if `used[j]` is `true`, skip to the next `j`.
*   For each pair `(words[i], words[j])`, check if `words[i]` is the reverse of `words[j]`. Since string length is 2, this means checking if `words[i].charAt(0) == words[j].charAt(1)` and `words[i].charAt(1) == words[j].charAt(0)`.
*   If they form a pair, increment the `pairs` counter, mark both strings as used (`used[i] = true`, `used[j] = true`), and break the inner loop to find a pair for the next `i`.
*   Return the final `pairs` count.

## Optimized Approach using a Hash Set
This approach improves upon the brute-force method by using a hash set to achieve a linear time complexity. We iterate through the words once, using the hash set to efficiently check if the reverse of the current word has been seen before.
**Time:** O(N * L), where N is the number of words and L is their length. We iterate through N words. For each word, reversing it takes O(L) time, and hash set operations (add/contains) take an average of O(L) time. Since L=2, this is effectively O(N). · **Space:** O(N * L), where N is the number of words and L is their length. In the worst case, the hash set stores all N words. Since L=2, this is effectively O(N).
**Pros:** Highly efficient with linear time complexity.; Scales well for larger inputs.; Simple and clean implementation.
**Cons:** Uses extra space for the hash set, which could be a concern for problems with very tight memory limits or extremely long strings (though not an issue with the given constraints).
### Explanation
The core idea is to iterate through the list of words and, for each word, quickly determine if its reverse counterpart has appeared earlier in the list. A `HashSet` is the ideal data structure for this, providing average O(1) time complexity for insertions and lookups (for fixed-length strings).

We initialize a counter for pairs and an empty `HashSet` to store the words we have encountered so far.

We iterate through each `word` in the `words` array. For each `word`, we first create its reversed version. Since all strings have a length of 2, reversing `word = "xy"` gives `"yx"`.

We then check if this `reversed_word` is present in our `HashSet`.

If the `reversed_word` exists in the set, it means we have found a pair (the current `word` and the `reversed_word` that was seen earlier). We increment our pair counter. Because each string can only be in one pair and all strings are distinct, we don't need to add the current `word` to the set or remove the `reversed_word`.

If the `reversed_word` is not in the set, it means we haven't found a pair for the current `word` yet. We add the current `word` to the `HashSet` so that it can be potentially matched with a word that appears later in the array.

After iterating through all the words, the counter will hold the total number of pairs found.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        int count = 0;
        Set<String> seen = new HashSet<>();

        for (String word : words) {
            String reversedWord = new StringBuilder(word).reverse().toString();
            if (seen.contains(reversedWord)) {
                count++;
            } else {
                seen.add(word);
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Initialize an empty `HashSet<String>` named `seen` to store words encountered so far.
*   Iterate through each `word` in the `words` array.
*   For each `word`, create its reversed version, `reversedWord`. For a 2-character string `s`, this can be done by swapping its characters.
*   Check if `seen` contains `reversedWord`.
*   If it does, a pair is found. Increment `count`.
*   If it does not, add the original `word` to the `seen` set to make it available for future matches.
*   After iterating through all words, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int maximumNumberOfStringPairs(String[] words) {
    Map<String, Integer> cnt = new HashMap<>(words.length);
    int ans = 0;
    for (String w : words) {
      ans += cnt.getOrDefault(w, 0);
      cnt.merge(new StringBuilder(w).reverse().toString(), 1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumNumberOfStringPairs(vector<string> &words) {
    unordered_map<string, int> cnt;
    int ans = 0;
    for (auto &w : words) {
      ans += cnt[w];
      reverse(w.begin(), w.end());
      cnt[w]++;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int: cnt = Counter() ans = 0 for w in words: ans += cnt[w] cnt[w[:: - 1]] += 1 return ans

```