Welcome to Subscribe On Youtube
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 ofwords[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 <= 50words[i].length == 2wordsconsists 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 string’s reversed string in the array $words$.
Traverse the array $words$, for each string $w$, we directly add the value of $cnt[w]$ to the answer, then increase the occurrence count of $w$’s reversed string by $1$.
After the traversal ends, we can get the maximum number of matches.
The time complexity is $O(L)$, and the space complexity is $O(L)$, where $L$ is the sum of the lengths of the strings in the array $words$.
-
class Solution { public int maximumNumberOfStringPairs(String[] words) { Map<String, Integer> cnt = new HashMap<>(words.length); int ans = 0; for (String w : words) { ans += cnt.getOrDefault(w, 0); cnt.merge(new StringBuilder(w).reverse().toString(), 1, Integer::sum); } return ans; } } -
class Solution { public: int maximumNumberOfStringPairs(vector<string>& words) { unordered_map<string, int> cnt; int ans = 0; for (auto& w : words) { ans += cnt[w]; reverse(w.begin(), w.end()); cnt[w]++; } return ans; } }; -
class Solution: def maximumNumberOfStringPairs(self, words: List[str]) -> int: cnt = Counter() ans = 0 for w in words: ans += cnt[w] cnt[w[::-1]] += 1 return ans -
func maximumNumberOfStringPairs(words []string) (ans int) { cnt := map[string]int{} for _, w := range words { ans += cnt[w] s := []byte(w) for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { s[i], s[j] = s[j], s[i] } cnt[string(s)]++ } return } -
function maximumNumberOfStringPairs(words: string[]): number { const cnt: Map<string, number> = new Map(); let ans = 0; for (const w of words) { ans += cnt.get(w) || 0; const s = w.split('').reverse().join(''); cnt.set(s, (cnt.get(s) || 0) + 1); } return ans; }