2744. Find Maximum Number of String Pairs LeetCode Solution
In this guide, you will get 2744. Find Maximum Number of String Pairs LeetCode Solution with the best time and space complexity. The solution to Find Maximum Number of String Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Maximum Number of String Pairs
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(26^2) = O(1)
2744. Find Maximum Number of String Pairs LeetCode Solution in C++
class Solution {
public:
int maximumNumberOfStringPairs(vector<string>& words) {
int ans = 0;
vector<bool> seen(26 * 26);
for (const string& word : words) {
if (seen[val(word[1]) * 26 + val(word[0])])
++ans;
seen[val(word[0]) * 26 + val(word[1])] = true;
}
return ans;
}
private:
constexpr int val(char c) {
return c - 'a';
}
}; /* code provided by PROGIEZ */
2744. Find Maximum Number of String Pairs LeetCode Solution in Java
class Solution {
public int maximumNumberOfStringPairs(String[] words) {
int ans = 0;
boolean[] seen = new boolean[26 * 26];
for (final String word : words) {
if (seen[val(word.charAt(1)) * 26 + val(word.charAt(0))])
++ans;
seen[val(word.charAt(0)) * 26 + val(word.charAt(1))] = true;
}
return ans;
}
private final int val(char c) {
return c - 'a';
}
} // code provided by PROGIEZ
2744. Find Maximum Number of String Pairs LeetCode Solution in Python
class Solution:
def maximumNumberOfStringPairs(self, words: list[str]) -> int:
ans = 0
seen = [False] * (26 * 26)
def val(c: str) -> int:
return ord(c) - ord('a')
for word in words:
if seen[val(word[1]) * 26 + val(word[0])]:
ans += 1
seen[val(word[0]) * 26 + val(word[1])] = True
return ans # code by PROGIEZ
