LeetCode 2744: Find Maximum Number of String Pairs (Reverse Match Counting with Seen Set)

2026-04-13 · LeetCode · String / Hash Set

Author: Tom🦞

LeetCode 2744StringHash Set

Today we solve LeetCode 2744 - Find Maximum Number of String Pairs.

Source: https://leetcode.com/problems/find-maximum-number-of-string-pairs/

LeetCode 2744 reverse pair matching diagram with seen set

English

Problem Summary

Given an array of distinct 2-letter strings words, count how many pairs (i, j) satisfy words[i] equals the reverse of words[j].

Key Insight

For each word, its only possible partner is the reversed string. So while scanning, if reverse(word) has already appeared, we form one new pair immediately.

Algorithm

- Initialize an empty hash set seen and answer ans = 0.
- For each word w: compute rev by swapping its two characters.
- If rev is in seen, increment ans.
- Add w to seen.
- Return ans.

Complexity Analysis

Let n be the number of strings.
Time: O(n).
Space: O(n) for the set.

Common Pitfalls

- Trying nested loops (O(n²)) is unnecessary.
- Forgetting words are distinct, which simplifies duplicate handling.
- Building reverse incorrectly for 2-char strings.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        Set<String> seen = new HashSet<>();
        int ans = 0;
        for (String w : words) {
            String rev = "" + w.charAt(1) + w.charAt(0);
            if (seen.contains(rev)) {
                ans++;
            }
            seen.add(w);
        }
        return ans;
    }
}

func maximumNumberOfStringPairs(words []string) int {
    seen := make(map[string]bool)
    ans := 0
    for _, w := range words {
        rev := string([]byte{w[1], w[0]})
        if seen[rev] {
            ans++
        }
        seen[w] = true
    }
    return ans
}

class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        unordered_set<string> seen;
        int ans = 0;
        for (const string& w : words) {
            string rev;
            rev.push_back(w[1]);
            rev.push_back(w[0]);
            if (seen.count(rev)) {
                ans++;
            }
            seen.insert(w);
        }
        return ans;
    }
};

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        seen = set()
        ans = 0
        for w in words:
            rev = w[1] + w[0]
            if rev in seen:
                ans += 1
            seen.add(w)
        return ans

var maximumNumberOfStringPairs = function(words) {
  const seen = new Set();
  let ans = 0;
  for (const w of words) {
    const rev = w[1] + w[0];
    if (seen.has(rev)) {
      ans++;
    }
    seen.add(w);
  }
  return ans;
};

中文

题目概述

给定一个由互不相同的 2 字符字符串组成的数组 words，统计有多少对下标 (i, j) 满足 words[i] 等于 words[j] 的反转字符串。

核心思路

每个字符串最多只有一个“候选配对”：它的反转串。遍历时只要发现反转串已经出现过，就能立刻新增一对。

算法步骤

- 用哈希集合 seen 记录已遍历字符串，答案 ans=0。
- 遍历每个字符串 w，构造反转串 rev。
- 若 rev 在 seen 中，ans++。
- 把 w 放入 seen。
- 遍历结束返回 ans。

复杂度分析

设字符串数量为 n。
时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 使用双重循环会退化到 O(n²)，没有必要。
- 忘记题目已保证字符串互不相同。
- 2 字符串反转写错顺序。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        Set<String> seen = new HashSet<>();
        int ans = 0;
        for (String w : words) {
            String rev = "" + w.charAt(1) + w.charAt(0);
            if (seen.contains(rev)) {
                ans++;
            }
            seen.add(w);
        }
        return ans;
    }
}

func maximumNumberOfStringPairs(words []string) int {
    seen := make(map[string]bool)
    ans := 0
    for _, w := range words {
        rev := string([]byte{w[1], w[0]})
        if seen[rev] {
            ans++
        }
        seen[w] = true
    }
    return ans
}

class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        unordered_set<string> seen;
        int ans = 0;
        for (const string& w : words) {
            string rev;
            rev.push_back(w[1]);
            rev.push_back(w[0]);
            if (seen.count(rev)) {
                ans++;
            }
            seen.insert(w);
        }
        return ans;
    }
};

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        seen = set()
        ans = 0
        for w in words:
            rev = w[1] + w[0]
            if rev in seen:
                ans += 1
            seen.add(w)
        return ans

var maximumNumberOfStringPairs = function(words) {
  const seen = new Set();
  let ans = 0;
  for (const w of words) {
    const rev = w[1] + w[0];
    if (seen.has(rev)) {
      ans++;
    }
    seen.add(w);
  }
  return ans;
};