algoadvance

Leetcode 2744. Find Maximum Number of String Pairs

Problem Statement

The problem requires finding the maximum number of string pairs (s1, s2) in a given array of strings such that one string is the reverse of the other. Each string can be paired with at most one other string. The aim is to return the maximum number of such pairs.

Clarifying Questions

To ensure a clear understanding of the problem, here are some questions that could be asked:

  1. Input Constraints: What is the range of the array size (number of strings) and the string lengths?
  2. Character Set: Are the strings composed of only lowercase letters, or can they contain uppercase letters as well?
  3. Uniqueness: Are all strings unique, or can there be duplicates?
  4. Case Sensitivity: Are string comparisons case-sensitive?

Assuming standard constraints: the input can be a mixture of uppercase and lowercase letters and the comparisons are case-sensitive. The constraints are such that we can efficiently handle them in typical coding interview settings.

Strategy

  1. Data Structure: Use a hash map (or an unordered map in C++) to keep track of the count of each string.
  2. Reverse Match: For each string in the array, check if its reverse already exists in the hash map with a positive count.
  3. Pair Counting: If a reverse match is found, form a pair and decrement the counts of both the current string and its reverse in the hash map.
  4. Result: Track and return the total count of such pairs.

Code

Here’s how the implementation might look in C++:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int findMaxStringPairs(vector<string>& strings) {
    unordered_map<string, int> stringCount;
    int pairCount = 0;

    // Populate the hash map with the count of each string
    for (const string& str : strings) {
        stringCount[str]++;
    }

    // Iterate through each string to find pairs
    for (const string& str : strings) {
        string reversedStr = str;
        reverse(reversedStr.begin(), reversedStr.end());

        // Check if this string can form a valid pair
        if (stringCount[str] > 0 && stringCount[reversedStr] > 0) {
            // Skip if they are the same string but there is only one instance of it
            if (str == reversedStr && stringCount[str] < 2) {
                continue;
            }
            // Form a pair and decrease the count
            pairCount++;
            stringCount[str]--;
            stringCount[reversedStr]--;
        }
    }

    return pairCount;
}

int main() {
    vector<string> strings = {"ab", "ba", "abc", "cba", "xy", "yx", "z", "zz"};
    cout << "Maximum number of string pairs: " << findMaxStringPairs(strings) << endl;
    return 0;
}

Time Complexity

  1. Hash Map Population: O(N), where N is the number of strings in the array.
  2. Reversing and Checking: Each reverse operation takes O(M) time where M is the average length of the strings. Since we do it for each string, this part totals to O(N * M).

Therefore, the overall time complexity is O(N * M), which is generally efficient for typical constraints found in coding interviews.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI