Find Maximum Number of String Pairs — LeetCode 2744 Python Solution

The problem

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

Example

Input

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

Output

2

Explanation

In this example, we can form 2 pair of strings in the following way:

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2744. Find Maximum Number of String Pairs is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems