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

  • 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;
    }
    
    

All Problems

All Solutions