Question

2744. Find Maximum Number of String Pairs

中文文档

Description

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].
• 0 <= i < j < words.length.

Return _the maximum number of pairs that can be formed from the array _words_._

Note that each string can belong in at most one pair.

 

Example 1:

Input: words = ["cd","ac","dc","ca","zz"]
Output: 2
Explanation: 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
Explanation: 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
Explanation: 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.

Solutions

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

We iterate through the array $words$. For each string $w$, we add the number of occurrences of its reversed string to the answer, then increment the count of $w$ by $1$.

Finally, we return the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $words$.

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

class Solution {
  public int maximumNumberOfStringPairs(String[] words) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int ans = 0;
    for (var w : words) {
      int a = w.charAt(0) - 'a', b = w.charAt(1) - 'a';
      ans += cnt.getOrDefault(b << 5 | a, 0);
      cnt.merge(a << 5 | b, 1, Integer::sum);
    }
    return ans;
  }
}

class Solution {
public:
  int maximumNumberOfStringPairs(vector<string>& words) {
    unordered_map<int, int> cnt;
    int ans = 0;
    for (auto& w : words) {
      int a = w[0] - 'a', b = w[1] - 'a';
      ans += cnt[b << 5 | a];
      cnt[a << 5 | b]++;
    }
    return ans;
  }
};

func maximumNumberOfStringPairs(words []string) (ans int) {
  cnt := map[int]int{}
  for _, w := range words {
    a, b := int(w[0]-'a'), int(w[1]-'a')
    ans += cnt[b<<5|a]
    cnt[a<<5|b]++
  }
  return
}

function maximumNumberOfStringPairs(words: string[]): number {
  const cnt: { [key: number]: number } = {};
  let ans = 0;
  for (const w of words) {
    const [a, b] = [w.charCodeAt(0) - 97, w.charCodeAt(w.length - 1) - 97];
    ans += cnt[(b << 5) | a] || 0;
    cnt[(a << 5) | b] = (cnt[(a << 5) | b] || 0) + 1;
  }
  return ans;
}