Leetcode 2744: Find Maximum Number of String Pairs

Input: The input consists of a list of distinct strings `words` where each string has exactly two lowercase English letters.

Example: words = ["cd", "ac", "dc", "ca", "zz"]

Constraints:

• 1 <= words.length <= 50

• words[i].length == 2

• All strings in words are distinct.

• words[i] contains only lowercase English letters.

Output: Return the maximum number of pairs that can be formed where one string is the reverse of the other.

Example: Output: 2

Constraints:

Goal: To count the maximum number of pairs where one string is the reverse of another in the given list.

Steps:

• Create an array to track previously seen string pairs.

• For each string in the list, check if its reverse has already been seen.

• If it has been seen, increase the count of valid pairs.

Goal: The array `words` has at least one element and at most 50 elements, and each string is exactly two characters long.

Steps:

• 1 <= words.length <= 50

• words[i].length == 2

• words[i] contains only lowercase English letters

Assumptions:

• The list of strings will always be distinct.

• Input: words = ["cd", "ac", "dc", "ca", "zz"]

• Explanation: The two valid pairs are: ["cd", "dc"] and ["ac", "ca"]. Hence, the output is 2.

• Input: words = ["ab", "ba", "cc"]

• Explanation: The valid pair is ["ab", "ba"]. Hence, the output is 1.

• Input: words = ["aa", "ab"]

• Explanation: No valid pairs can be formed, so the output is 0.

Approach: The approach involves creating a simple check to identify valid pairs by tracking seen pairs and counting valid combinations.

Observations:

• The problem can be solved by checking if a reversed string exists in the list.

• We can leverage a hash-based approach to store previously seen strings and their reverses.

Steps:

• Create a 2D array to track which string pairs have been seen.

• Iterate through the list of words and check if its reverse has been encountered.

• For each pair, increment the valid pair count and mark the pair as seen.

Empty Inputs:

• The problem guarantees that the list will never be empty.

Large Inputs:

• The solution must handle lists with up to 50 elements efficiently.

Special Values:

• When all words are the same or have no reversals, no pairs can be formed.

Constraints:

• All words are distinct and consist of two lowercase letters, making it easy to check for reversals.

int maximumNumberOfStringPairs(vector<string>& words) {
int vis[676] = {}, res = 0;
for (const auto &w : words) {
    res += vis[(w[1] - 'a') * 26 + w[0] - 'a'];
    vis[(w[0] - 'a') * 26 + w[1] - 'a'] = true;
}
return res;
}

1 : Variable Initialization

int maximumNumberOfStringPairs(vector<string>& words) {

Defines the main function to calculate the maximum number of string pairs from a list of words.

2 : Array Initialization

int vis[676] = {}, res = 0;

Initializes an array `vis` of size 676 to track pairs of characters, and a result variable `res` to store the number of valid pairs.

3 : Looping

for (const auto &w : words) {

Iterates through each word in the `words` array.

4 : Frequency Calculation

    res += vis[(w[1] - 'a') * 26 + w[0] - 'a'];

Checks the frequency of the reversed pair of characters in the `vis` array and adds the count to the result.

5 : Array Update

    vis[(w[0] - 'a') * 26 + w[1] - 'a'] = true;

Marks the current pair of characters as encountered in the `vis` array.

6 : Return Statement

return res;

Returns the total count of valid string pairs found.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear with respect to the number of words, as each word is checked once.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is linear, as we store a small number of possible string reversals.

Leetcode 2744: Find Maximum Number of String Pairs

Explore →