#2744

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Maximum Number of String Pairs

Find the maximum number of pairs of distinct strings from an array where one string is the reverse of the other.

Problem Statement

Given a list of distinct strings, each with two characters, your task is to find how many pairs of strings can be formed such that one string is the reverse of the other.

Return the maximum number of such pairs possible from the given array of strings.

Examples

Example 1

Input: words = ["cd","ac","dc","ca","zz"]

Output: 2

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

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

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.

Solution Approach

Hash Table Lookup

Use a hash table to store the words from the array, then for each word, check if its reverse exists in the hash table. Count each valid pair, and ensure you don’t count pairs more than once.

Array Scanning

Scan through the array and for each word, check its reverse using the hash table. This ensures an efficient solution as opposed to brute force.

Distinct Strings

Since all strings are distinct, checking for the reverse of each word ensures no duplicates are counted, simplifying the logic and improving efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of words and the lookups in the hash table. The space complexity depends on the size of the hash table used to store the words.

What Interviewers Usually Probe

Look for candidates who use a hash table for efficient lookups.
Evaluate if the candidate ensures no duplicate pairs are counted.
Assess the candidate’s understanding of leveraging hash tables to optimize array scanning.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reverse each word and check for its pair.
Not using a hash table, resulting in slow lookups.
Miscounting pairs when both words are part of the same pair, leading to duplication.

Follow-up variants

Extend the problem by increasing the length of the words.
Use a different data structure to store the words, such as a set.
Modify the problem by considering multi-character words.

FAQ

What is the optimal way to solve 'Find Maximum Number of String Pairs'?

The optimal solution uses a hash table to store the strings and checks for the reverse of each word efficiently.

How do I prevent counting duplicate pairs?

By ensuring each pair is counted only once, for example by marking words that have already been paired.

What is the time complexity of this problem?

The time complexity depends on the number of words and the hash table lookups, typically O(n).

Can this problem be solved without a hash table?

Yes, but using a hash table ensures more efficient lookups and reduces time complexity.

What other data structures could be used for this problem?

You could use a set or a list, but hash tables provide the most efficient solution for this problem.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $cnt$ to store the number of occurrences of each reversed string in the array $words$.

1

2

3

4

5

6

7

8

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        cnt = Counter()
        ans = 0
        for w in words:
            ans += cnt[w[::-1]]
            cnt[w] += 1
        return ans

Continue Practicing

#3522 calculate score after performing instructions #2766 relocate marbles #2707 extra characters in a string