Problem statement

You are given an array words of distinct strings, each exactly two lowercase letters long.

Two indices i < j can be paired when words[i] is the reverse of words[j]. Every string may belong to at most one pair.

Return the maximum number of pairs that can be formed.

Example 1

Input: words = ["cd","ac","dc","ca","zz"]
Output: 2
Explanation: `cd` pairs with `dc` and `ac` pairs with `ca`. `zz` is its own reverse, but no other copy of it exists.

Example 2

Input: words = ["ab","ba","cc"]
Output: 1

Example 3

Input: words = ["aa","ab"]
Output: 0
Explanation: A palindrome cannot pair with itself — a pair needs two different indices.

Constraints

• 1 <= words.length <= 50
• words[i].length == 2
• words consists of distinct strings
• words[i] contains only lowercase English letters

Hints for Find Maximum Number of String Pairs

1. Hint 1

   Because the words are distinct, a word has at most one possible partner: its reverse. So no choice is ever involved.

2. Hint 2

   Walk the list once and remember the words seen so far.

3. Hint 3

   Before recording a word, ask whether its reverse is already recorded — if so, that is one more pair.

How to solve Find Maximum Number of String Pairs

With distinct words, each word's only candidate partner is its reverse, and that reverse occurs at most once — so the pairs are forced and you only have to count them. A set of the words seen so far finds each pair when its second word arrives.

Approach

1. Keep an empty set seen and a counter pairs = 0.
2. For each word w, if reverse(w) is in seen, increment pairs.
3. Add w to seen.
4. Return pairs.

Why it works

A word w can only pair with reverse(w), and since words are distinct there is exactly zero or one such word. Pairs therefore never compete for a word, and each is counted exactly once — when its later member is processed. A palindrome such as zz would need a second copy of itself, which distinctness rules out, and checking before inserting keeps it from matching itself.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Inserting the word before checking would let a palindrome pair with itself.
• With only 26 × 26 possible words, a 26 × 26 boolean table replaces the set in languages without one.

Reference solution

Python

from typing import List

def maximumNumberOfStringPairs(words: List[str]) -> int:
    seen = set()
    pairs = 0
    for w in words:
        if w[::-1] in seen:
            pairs += 1
        seen.add(w)
    return pairs

Java

public static int maximumNumberOfStringPairs(String[] words) {
    boolean[][] seen = new boolean[26][26];
    int pairs = 0;
    for (String w : words) {
        int a = w.charAt(0) - 'a', b = w.charAt(1) - 'a';
        if (seen[b][a]) pairs++;
        seen[a][b] = true;
    }
    return pairs;
}

C++

int maximumNumberOfStringPairs(vector<string>& words) {
    bool seen[26][26] = {};
    int pairs = 0;
    for (const string& w : words) {
        int a = w[0] - 'a', b = w[1] - 'a';
        if (seen[b][a]) pairs++;
        seen[a][b] = true;
    }
    return pairs;
}

JavaScript

var maximumNumberOfStringPairs = function(words) {
    var seen = {};
    var pairs = 0;
    for (var i = 0; i < words.length; i++) {
        var w = words[i];
        if (seen[w[1] + w[0]]) pairs++;
        seen[w] = true;
    }
    return pairs;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy