Problem Description

You are given a 0-indexed array words containing distinct strings. Your task is to find the maximum number of pairs that can be formed from this array.

Two strings can form a pair if they meet these conditions:

• One string is exactly the reverse of the other string
• They are at different positions in the array where the first position index is less than the second position index (0 <= i < j < words.length)
• Each string can be used in at most one pair

For example, if you have words = ["cd", "ac", "dc", "ca", "zz"], you can form 2 pairs:

• "cd" (index 0) pairs with "dc" (index 2) because "cd" reversed is "dc"
• "ac" (index 1) pairs with "ca" (index 3) because "ac" reversed is "ca"
• "zz" cannot form a pair because there's no other "zz" in the array (its reverse is itself)

The solution uses a hash table to count occurrences. As we iterate through each word w:

1. We check if the reversed version of w (written as w[::-1]) already exists in our counter
2. If it does, we can form a pair, so we add that count to our answer
3. We then add the current word w to our counter for future potential pairs

This approach ensures we only count valid pairs where i < j since we're checking for reversed strings that appeared before the current position.

Intuition

The key insight is that we need to find pairs where one string is the reverse of another, and we want to maximize the number of such pairs. Since each string can only be used once, we need an efficient way to match strings with their reverses.

Think about what happens when we traverse the array from left to right. For each string we encounter, we want to know: "Has the reverse of this string appeared before?" If it has, we can form a pair immediately.

This naturally leads us to use a hash table approach. As we go through the array:

• For the current string, check if its reverse has been seen before
• If yes, we can form pairs with all previous occurrences of the reversed string
• Then, record the current string for future potential matches

Why does this work? Consider the constraint i < j. When we're at position j, we only need to look backwards for potential pairs at positions i where i < j. By maintaining a counter of all strings we've seen so far, we automatically satisfy this ordering constraint.

The beauty of this approach is that we handle the pairing greedily - whenever we find a match, we count it immediately. Since the problem asks for the maximum number of pairs and each string can only be used once, this greedy approach is optimal. We don't need to worry about "saving" a string for a better match later because any valid pairing contributes equally to our count.

The time complexity is O(n) where n is the number of words, making this solution very efficient compared to checking all possible pairs which would be O(n²).

Solution Approach

The solution uses a hash table to efficiently track and match strings with their reverses. Here's how the implementation works:

Data Structure: We use a Counter object (hash table) called cnt to store the frequency of each string we've encountered so far.

Algorithm Steps:

1. Initialize variables:

   • cnt = Counter() - An empty hash table to track string occurrences
   • ans = 0 - Counter for the number of pairs formed

2. Iterate through each word in the words array:

   for w in words:

3. Check for reverse match:

   ans += cnt[w[::-1]]

   • w[::-1] generates the reversed string of w
   • cnt[w[::-1]] returns the count of how many times the reversed string has appeared before
   • We add this count to ans because each previous occurrence of the reversed string can form a pair with the current string

4. Update the counter:

   cnt[w] += 1

   • Record the current string in our hash table for future potential matches
   • This happens after checking for pairs to ensure we don't pair a string with itself

Why this works:

• The order of operations is crucial: we check for matches before adding the current string
• This ensures we only count pairs where i < j (the reversed string appeared at an earlier index)
• Each string is counted exactly once in a pair because we only look backwards

Example walkthrough with words = ["cd", "ac", "dc", "ca"]:

• Process "cd": cnt["dc"] = 0, no pair formed, update cnt["cd"] = 1
• Process "ac": cnt["ca"] = 0, no pair formed, update cnt["ac"] = 1
• Process "dc": cnt["cd"] = 1, one pair formed! ans = 1, update cnt["dc"] = 1
• Process "ca": cnt["ac"] = 1, one pair formed! ans = 2, update cnt["ca"] = 1
• Final answer: 2 pairs

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: words = ["ab", "ba", "cc", "ba", "ab", "ba"]

We'll trace through the algorithm step by step:

Initial State:

• cnt = {} (empty counter)
• ans = 0 (no pairs yet)

Step 1 - Process "ab" (index 0):

• Check if reverse "ba" exists in cnt: No (count = 0)
• Add 0 to ans: ans = 0
• Update counter: cnt = {"ab": 1}

Step 2 - Process "ba" (index 1):

• Check if reverse "ab" exists in cnt: Yes! (count = 1)
• Add 1 to ans: ans = 1 (formed pair: "ab"[0] with "ba"[1])
• Update counter: cnt = {"ab": 1, "ba": 1}

Step 3 - Process "cc" (index 2):

• Check if reverse "cc" exists in cnt: No (count = 0)
• Note: "cc" reversed is still "cc", but there's no previous "cc"
• Add 0 to ans: ans = 1
• Update counter: cnt = {"ab": 1, "ba": 1, "cc": 1}

Step 4 - Process "ba" (index 3):

• Check if reverse "ab" exists in cnt: Yes! (count = 1)
• Add 1 to ans: ans = 2 (formed pair: "ab"[0] with "ba"[3])
• Note: The "ab" at index 0 hasn't been used yet, so it can pair
• Update counter: cnt = {"ab": 1, "ba": 2}

Step 5 - Process "ab" (index 4):

• Check if reverse "ba" exists in cnt: Yes! (count = 2)
• Add 2 to ans: ans = 4 (can form pairs with both "ba"[1] and "ba"[3])
• Update counter: cnt = {"ab": 2, "ba": 2}

Step 6 - Process "ba" (index 5):

• Check if reverse "ab" exists in cnt: Yes! (count = 2)
• Add 2 to ans: ans = 6 (can form pairs with "ab"[0] and "ab"[4])
• Update counter: cnt = {"ab": 2, "ba": 3}

Final Answer: 6 pairs

The key insight is that when we encounter a string, we can form as many pairs as there are previous occurrences of its reverse. This greedy approach maximizes the number of pairs while respecting the constraint that each string position can only be used once.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m), where n is the length of the array words and m is the average length of each word string. This is because:

• The algorithm iterates through all n words once
• For each word w, it performs w[::-1] which takes O(m) time to reverse the string
• The hash table operations (lookup and insertion) take O(m) time since strings are used as keys and comparing/hashing strings requires examining their characters

The space complexity is O(n × m). This is because:

• The Counter dictionary cnt can store up to n unique words as keys
• Each key (word) has length m on average, so storing all keys requires O(n × m) space
• The reversed string w[::-1] creates a temporary string of length m, but this doesn't affect the overall space complexity

Note: The reference answer simplifies this to O(n) by likely assuming constant-length strings or treating string operations as O(1), which is a common simplification in some contexts where string length is bounded by a small constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Pair a Palindrome with Itself

The Pitfall: When encountering palindromes (strings that read the same forwards and backwards, like "aa", "aba"), developers might incorrectly count them as pairs since the string equals its own reverse.

Why it happens: The condition cnt[w[::-1]] will find the palindrome itself if we're not careful about the order of operations.

Example of incorrect approach:

# WRONG: Adding to counter before checking
for word in words:
    word_count[word] += 1  # Adding first (WRONG!)
    pair_count += word_count[word[::-1]]

With words = ["aa", "bb"], this would incorrectly count "aa" as forming a pair with itself.

The Solution: The correct implementation checks for the reverse BEFORE adding the current word to the counter. This ensures a palindrome won't match with itself:

# CORRECT: Check first, then add
for word in words:
    pair_count += word_count[word[::-1]]  # Check first
    word_count[word] += 1  # Then add

2. Double-Counting Pairs

The Pitfall: Trying to count all possible matches at once without considering the constraint that each string can only be used once.

Example of incorrect approach:

# WRONG: This might count the same pair multiple times
for i in range(len(words)):
    for j in range(i+1, len(words)):
        if words[i] == words[j][::-1]:
            pair_count += 1

The Solution: The hash table approach naturally prevents double-counting because once we've found a match for a string with its reverse, we only increment the counter by the exact number of available reverses seen so far.

3. Handling Duplicate Strings Incorrectly

The Pitfall: Although the problem states the array contains "distinct strings", if there were duplicates, a naive approach might pair a string with another instance of the same string at a different index.

Example scenario: If words = ["ab", "ba", "ab"], we should form 2 pairs, not 1.

The Solution: The counter-based approach handles this correctly by counting occurrences. Each "ab" can pair with each previously seen "ba", giving us the correct count automatically through pair_count += word_count[word[::-1]].