LeetCode Problem 2744

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String, Simulation

Solution

LeetCode 2744 - Find Maximum Number of String Pairs

Problem Understanding

This problem gives us an array words containing distinct strings. Every string has length exactly 2, and all strings consist of lowercase English letters.

We can form a pair between two strings words[i] and words[j] when:

• i < j
• One string is exactly the reverse of the other

For example, "ab" and "ba" form a valid pair because reversing "ab" produces "ba".

Our goal is to determine the maximum number of such pairs that can be formed. Each string may participate in at most one pair.

Since all strings are distinct, a string can never appear twice in the array. This guarantee simplifies the problem significantly because if a reverse string exists, there is exactly one possible partner for that string.

The input represents a collection of two-character strings, and the output is the total number of disjoint reverse-string pairs that can be formed.

The constraints are very small:

• 1 <= words.length <= 50
• Every string has length 2
• All strings are distinct

A brute-force solution would already be fast enough because there are at most 50 strings. However, there is a cleaner and more efficient hash set approach that directly exploits the reverse-string relationship.

Some important edge cases include:

• No reverse pairs exist at all.
• Multiple independent pairs exist.
• Strings such as "aa" reverse to themselves. Since all strings are distinct, there can be only one "aa", so it can never form a pair.
• The reverse string may appear before or after the current string in the array.
• The array may contain only one string.

Approaches

Brute Force

The most straightforward approach is to examine every possible pair of indices (i, j) where i < j.

For each pair, reverse one string and compare it with the other. If they match, we have found a valid pair and increase the answer.

Because every string is distinct, each valid reverse relationship corresponds to exactly one pair, so counting such pairs produces the correct answer.

This approach is correct because it explicitly checks every possible pair. However, it performs unnecessary comparisons and does not take advantage of the fact that we can quickly look up whether a reversed string exists.

Optimal Hash Set Approach

The key observation is that for any word, we only care whether its reversed version has already been seen.

As we iterate through the array:

• Compute the reversed version of the current word.
• If the reversed string already exists in a hash set, we have discovered a valid pair.
• Otherwise, store the current word in the set for future lookups.

Because every string is distinct, each pair is counted exactly once, specifically when the second member of the pair is encountered.

Hash set lookups are constant time on average, giving a very efficient solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every pair of strings
Optimal	O(n)	O(n)	Use a hash set to detect reversed strings

Algorithm Walkthrough

1. Create an empty hash set called seen.
2. Create a variable pairs and initialize it to 0.
3. Iterate through each word in words.
4. Reverse the current word. Since every word has length 2, reversing is very cheap.
5. Check whether the reversed string already exists in seen.
6. If it exists, increment pairs because we have found a valid reverse-string pair. The reverse must have appeared earlier in the array.
7. Add the current word to seen so future words can match against it.
8. Continue until all words have been processed.
9. Return pairs.

Why it works

The algorithm maintains the invariant that seen contains exactly the words processed so far.

When processing a word w, if its reverse rev(w) is already in seen, then we have found the unique valid partner for w. Since all strings are distinct, this pair can only be discovered once, when the later word in the pair is processed. Therefore every valid pair is counted exactly once, and no invalid pair is counted.

Python Solution

from typing import List

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        seen = set()
        pairs = 0

        for word in words:
            if word[::-1] in seen:
                pairs += 1

            seen.add(word)

        return pairs

The implementation follows the algorithm directly.

A hash set named seen stores all previously processed words. For each word, the expression word[::-1] creates its reversed version. If that reversed string already exists in the set, a valid pair has been found, so the answer is increased.

After the lookup, the current word is inserted into the set. This ensures that future words can match against it. Once all words have been processed, the accumulated pair count is returned.

Go Solution

func maximumNumberOfStringPairs(words []string) int {
	seen := make(map[string]bool)
	pairs := 0

	for _, word := range words {
		reversed := string([]byte{word[1], word[0]})

		if seen[reversed] {
			pairs++
		}

		seen[word] = true
	}

	return pairs
}

The Go implementation uses a map[string]bool as a hash set.

Since every string has length exactly 2, reversing a string is extremely simple. We construct a new string using the second character followed by the first character. The remainder of the algorithm is identical to the Python version.

There are no concerns about integer overflow because the maximum possible answer is at most 25, given that there are at most 50 strings.

Worked Examples

Example 1

Input:

["cd","ac","dc","ca","zz"]

Step	Current Word	Reverse	Seen Before Processing	Pair Found?	Pairs
1	cd	dc	{}	No	0
2	ac	ca	{cd}	No	0
3	dc	cd	{cd, ac}	Yes	1
4	ca	ac	{cd, ac, dc}	Yes	2
5	zz	zz	{cd, ac, dc, ca}	No	2

Final answer:

2

Example 2

Input:

["ab","ba","cc"]

Step	Current Word	Reverse	Seen Before Processing	Pair Found?	Pairs
1	ab	ba	{}	No	0
2	ba	ab	{ab}	Yes	1
3	cc	cc	{ab, ba}	No	1

Final answer:

1

Example 3

Input:

["aa","ab"]

Step	Current Word	Reverse	Seen Before Processing	Pair Found?	Pairs
1	aa	aa	{}	No	0
2	ab	ba	{aa}	No	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass through the array, constant-time hash lookups
Space	O(n)	The hash set may store all words

The algorithm processes each word exactly once. Each iteration performs a constant amount of work: reversing a two-character string, checking membership in a hash set, and inserting into the hash set. Therefore the total running time is linear in the number of words.

The additional memory comes from storing previously seen words. In the worst case, all words are stored, giving linear space complexity.

Test Cases

sol = Solution()

assert sol.maximumNumberOfStringPairs(["cd", "ac", "dc", "ca", "zz"]) == 2  # example 1
assert sol.maximumNumberOfStringPairs(["ab", "ba", "cc"]) == 1  # example 2
assert sol.maximumNumberOfStringPairs(["aa", "ab"]) == 0  # example 3

assert sol.maximumNumberOfStringPairs(["ab"]) == 0  # single element
assert sol.maximumNumberOfStringPairs(["ab", "ba"]) == 1  # one pair
assert sol.maximumNumberOfStringPairs(["ab", "cd"]) == 0  # no pairs

assert sol.maximumNumberOfStringPairs(["ab", "ba", "cd", "dc"]) == 2  # multiple pairs
assert sol.maximumNumberOfStringPairs(["ab", "cd", "dc", "ba"]) == 2  # pairs found later

assert sol.maximumNumberOfStringPairs(["aa"]) == 0  # self-reversing string alone
assert sol.maximumNumberOfStringPairs(["aa", "bb", "cc"]) == 0  # all self-reversing

assert sol.maximumNumberOfStringPairs(
    ["ab", "ba", "cd", "dc", "ef", "fe", "gh", "hg"]
) == 4  # many independent pairs

assert sol.maximumNumberOfStringPairs(
    ["ab", "bc", "cd", "de", "ef"]
) == 0  # larger no-pair case

Test Summary

Test	Why
["cd","ac","dc","ca","zz"]	Validates multiple pairs
["ab","ba","cc"]	Validates a single pair
["aa","ab"]	Validates no pair formation
["ab"]	Minimum size input
["ab","ba"]	Simplest successful pair
["ab","cd"]	No matching reverses
["ab","ba","cd","dc"]	Multiple independent pairs
["ab","cd","dc","ba"]	Reverse strings appear later
["aa"]	Self-reversing string alone
["aa","bb","cc"]	Multiple self-reversing strings
["ab","ba","cd","dc","ef","fe","gh","hg"]	Larger number of pairs
["ab","bc","cd","de","ef"]	Larger input with zero matches

Edge Cases

Self-Reversing Strings

Strings such as "aa", "bb", or "cc" are equal to their own reverse. A common mistake is to assume they can form pairs with themselves. Since all strings in the array are distinct, such a string appears at most once. Therefore it can never form a valid pair. The hash-set solution handles this naturally because no identical string will appear later.

Single Element Array

When the array contains only one string, no pair can possibly be formed because a pair requires two different indices. The algorithm processes the lone string, finds no reverse in the set, and correctly returns 0.

Reverse Appears Earlier or Later

A valid pair may appear in either order within the array. For example, "ab" may appear before "ba", or "ba" may appear before "ab". The algorithm works in both situations because it always checks whether the reverse has already been seen. Exactly one of the two strings will encounter its partner in the set, ensuring the pair is counted once.

Multiple Independent Pairs

The array may contain several unrelated reverse-string pairs. Because every valid pair involves distinct strings and the input contains no duplicates, each pair is discovered independently. The hash set stores all previously seen words, allowing every valid pair to be found without interference from the others.