Find Maximum Number of String Pairs

Easy

#2469Time: 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.

Data structures

Array Hash Table String

Prompt

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

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 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.

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.

1class Solution {2    public int maximumNumberOfStringPairs(String[] words) {3        int n = words.length;4        int count = 0;5        boolean[] used = new boolean[n];6 7        for (int i = 0; i < n; i++) {8            if (used[i]) {9                continue;10            }11            for (int j = i + 1; j < n; j++) {12                if (used[j]) {13                    continue;14                }15                String s1 = words[i];16                String s2 = words[j];17                // Since length is 2, reversing is just swapping characters.18                if (s1.charAt(0) == s2.charAt(1) && s1.charAt(1) == s2.charAt(0)) {19                    count++;20                    used[i] = true;21                    used[j] = true;22                    break; // words[i] is now paired, move to the next i23                }24            }25        }26        return count;27    }28}

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.

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.

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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int maximumNumberOfStringPairs(String[] words) {6        int count = 0;7        Set<String> seen = new HashSet<>();8 9        for (String word : words) {10            String reversedWord = new StringBuilder(word).reverse().toString();11            if (seen.contains(reversedWord)) {12                count++;13            } else {14                seen.add(word);15            }16        }17        return count;18    }19}

Complexity

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).

Trade-offs

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).

Solutions

Solution

1class Solution {2public3  int maximumNumberOfStringPairs(String[] words) {4    Map<String, Integer> cnt = new HashMap<>(words.length);5    int ans = 0;6    for (String w : words) {7      ans += cnt.getOrDefault(w, 0);8      cnt.merge(new StringBuilder(w).reverse().toString(), 1, Integer : : sum);9    }10    return ans;11  }12}

1class Solution {2public:3  int maximumNumberOfStringPairs(vector<string> &words) {4    unordered_map<string, int> cnt;5    int ans = 0;6    for (auto &w : words) {7      ans += cnt[w];8      reverse(w.begin(), w.end());9      cnt[w]++;10    }11    return ans;12  }13};

1class Solution:2    def maximumNumberOfStringPairs(self, words: List[str]) -> int: cnt = Counter() ans = 0 for w in words: ans += cnt[w] cnt[w[:: - 1]] += 1 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.

← Previous

Previous problem

Next problem