Find Maximum Number of String Pairs
EasyPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a counter
pairsto 0. - Create a boolean array
usedof the same size aswords, initialized tofalse. This will track which strings have already been paired. - Use a nested loop to iterate through all pairs of indices
(i, j)such that0 <= i < j < words.length. - In the outer loop, if
used[i]istrue, skip to the nexti. - In the inner loop, if
used[j]istrue, skip to the nextj. - For each pair
(words[i], words[j]), check ifwords[i]is the reverse ofwords[j]. Since string length is 2, this means checking ifwords[i].charAt(0) == words[j].charAt(1)andwords[i].charAt(1) == words[j].charAt(0). - If they form a pair, increment the
pairscounter, mark both strings as used (used[i] = true,used[j] = true), and break the inner loop to find a pair for the nexti. - Return the final
pairscount.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.