Find Maximum Number of String Pairs - Solution & Explanation
Problem Statement
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 ofwords[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 <= 50words[i].length == 2wordsconsists of distinct strings.words[i]contains only lowercase English letters.
Approach Overview
Problem Overview: You are given an array of two‑character strings. A valid pair exists when one string is the reverse of another string in the array (for example, "ab" and "ba"). The goal is to count the maximum number of such disjoint pairs.
Approach 1: Brute Force Pair Checking (O(n2) time, O(1) space)
The direct method compares every string with every other string. Iterate through the array using two nested loops. For each string words[i], compute its reverse and check if it matches any words[j] where j > i. If a match is found, count the pair and ensure those indices are not reused. This approach relies only on basic iteration and string comparison, making it useful for understanding the core requirement of the problem. However, because it performs pairwise comparisons across the array, the time complexity grows quadratically as the input size increases.
Even though the brute force method works within constraints for small inputs, it becomes inefficient when the number of strings increases. The algorithm performs repeated reverse checks and comparisons, which makes it a good baseline but not the best choice when an optimized lookup structure is available.
Approach 2: Hash Map for Quick Lookups (O(n) time, O(n) space)
A more efficient solution uses a hash-based structure to track strings you've already seen. Iterate through the array once. For each string, compute its reversed form (for example, "ab" → "ba"). Before storing the current string, check whether the reversed string already exists in the hash map or hash set. If it does, you found a valid pair, so increment the pair count and remove the stored string to avoid reuse.
This works because a hash lookup runs in constant time on average. Instead of comparing against every other element, you immediately determine whether the complementary reversed string exists. Each string is processed once, making the total runtime linear relative to the number of elements.
The approach is a common pattern in problems involving complements or reverse matching. The hash structure acts as a memory of previously seen elements and eliminates redundant comparisons. Problems involving string transformations often combine hash table lookups with simple string operations while iterating through an array.
Recommended for interviews: Start by explaining the brute force method to demonstrate that you understand the definition of a valid pair. Then move to the hash map approach, which reduces the runtime from quadratic to linear. Interviewers usually expect the hash-based solution because it shows awareness of efficient lookups and common optimization patterns.
Approach 1: Approach 1: Brute Force Pair Checking
This approach involves iterating through each possible pair of strings in the array and checking if one is the reverse of the other. Given the constraints (with length at most 50), a simple nested loop can be employed to compare each string with every other string for reversibility.
Though this method isn't the most efficient due to its O(n^2) complexity, it is straightforward and easy to implement, especially given the manageable input size limit.
This solution involves using a nested loop to iterate through each pair of words in the words array. The isReverse function checks if one word is the reverse of the other. The used array keeps track of which words have been used in a pair to ensure that each can be used only once. The result is the total count of such pairs.
Complexity
Time Complexity: O(n^2), where n is the length of the words array, due to the nested iteration over all pairs.
Space Complexity: O(n), due to the used array.
Approach 2: Approach 2: Hash Map for Quick Lookups
Instead of checking each pair naively, we can use a hash map to store each word and perform reverse checks for faster lookups. This allows us to efficiently determine if a word's reverse exists among the previously seen words, effectively reducing unnecessary comparisons.
This approach leverages the hash map's average constant time complexity for lookups to enhance performance over the brute force method.
This C approach utilizes early termination by breaking after a successful pair is found in inner loop comparisons, supplemented with a reverse string generator. Since direct hash maps aren't supported, the method mimics hash behavior by marking used pairs.
Complexity
Time Complexity: O(n^2) - Because the absence of hash data structures leads back to nested iterations though slightly optimized by early breaks.
Space Complexity: O(n) - For usage tracking.
Approach 3: Hash Table
We can use a hash table cnt to store the number of occurrences of each reversed string in the array words.
We iterate through the array words. For each string w, we add the number of occurrences of its reversed string to the answer, then increment the count of w by 1.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array words.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Pair Checking | Time Complexity: O(n^2), where n is the length of the Space Complexity: O(n), due to the |
| Approach 2: Hash Map for Quick Lookups | Time Complexity: O(n^2) - Because the absence of hash data structures leads back to nested iterations though slightly optimized by early breaks. Space Complexity: O(n) - For usage tracking. |
| Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Small input sizes or when demonstrating the baseline logic during interviews |
| Hash Map for Quick Lookups | O(n) | O(n) | General case and interview‑expected solution using constant‑time lookups |
Video Solution
6892. Find Maximum Number of String Pairs | Leetcode | Biweekly Contest 107 | Solution Code. • Optimization • 1,031 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Maximum Number of String Pairs easy or hard?
Find Maximum Number of String Pairs Python/Java solution
How to solve Find Maximum Number of String Pairs in O(n)?
What is the best approach for Find Maximum Number of String Pairs?
Is Find Maximum Number of String Pairs asked at Google/Amazon/Meta?
What data structure is used in Find Maximum Number of String Pairs?
What is the time complexity of Find Maximum Number of String Pairs?
Ready to solve this problem?
Practice Find Maximum Number of String Pairs with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor