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:
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 <= 50words[i].length == 2words consists of distinct strings.words[i] contains only lowercase English letters.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
Leetcode - Max Number of K-Sum Pairs (Python) • Timothy H Chang • 8,391 views views
Watch 9 more video solutions →Practice Find Maximum Number of String Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor