2744. Find Maximum Number of String Pairs

EasyArrayHash TableStringSimulation

Problem Description

In this problem, you are given an array words where each element is a distinct string. A pair of strings (words[i] and words[j]) can be formed if one string is the reverse of the other and the indices i and j meet the condition that i < j. The goal is to find the maximum number of such unique pairs from the array words. It's important to note that a string can only be used in one pair, meaning once a string has been paired, it cannot be part of another pair.

Intuition

To solve the problem, we need to keep track of strings that we can form a pair with. As the condition requires one string to be the reverse of another, for any given string, we can look for its reverse in the array. The approach involves iterating through the array, checking if we have previously encountered the reverse of the current string. If so, we have found a viable pair, and we increment our count of pairs.

We utilize a counter (a special dictionary in Python that counts the occurrences of each element in an iterable) to keep track of how many times we have encountered the reversed strings. Each time we find a string, we look up its reverse in the counter. If the reverse is present, that means we can form a pair, so we increment our answer by the count of the reverse (which, due to the problem's constraints, will always be 1), and then we increment the counter for the reverse of the current string (which prepares us for future potential pairs). This solution ensures that we count each possible pair exactly once and efficiently solves the problem in linear time.

Solution Approach

The implementation of the solution uses a Counter, which is a subclass of dictionary provided by the Python collections module. It's specifically designed to count hashable objects in an iterable. In the context of this problem, it is used to keep track of the occurrence of each string's reverse within the words array.

Here's a step-by-step approach to how the code works:

We initialize a Counter object named cnt and a variable named ans set to 0, which will keep track of the total number of pairs found.
The for loop iterates through each word in the given words array.
Each iteration performs two operations:
- It increments the answer ans by the current count of the word in the counter. This count represents the number of times the reverse of this word has been encountered before in the array. Because of the problem constraints (distinct strings and each string can be part of at most one pair), this condition indicates that we've found a pair.
- It then increments the count of the reversed word in the counter by 1. This will help to identify a pair when we meet the corresponding reverse in subsequent iterations.
Finally, after processing all the words, we return ans, which holds the maximum number of unique pairs we can form.

In summary, the algorithm utilizes the hash-based lookups provided by the Counter to check for potential pairs efficiently. This approach is essentially a one-pass solution since each word in the array is looked at exactly once, making the algorithm O(n) where n is the number of words in the array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the following words array:

words = ["abcd", "dcba", "lls", "s", "sssll"]

First, we initialize a Counter named cnt to keep track of the reversed words we encounter and a variable ans to count the number of pairs.

cnt = Counter()
ans = 0

As we iterate through the words array:

For the first word "abcd", its reverse is "dcba", which is not yet in cnt, so no pair is formed. Update cnt with the reverse of the current word.

cnt["dcba"] = 1
ans = 0

The next word "dcba" has a reverse "abcd", which is already in cnt. It's a match! Increment ans by 1 and update cnt for the reverse "badc".

cnt["badc"] = 1
ans = 1

The third word "lls" does not have its reverse in cnt, so no new pair is formed yet.

cnt["sll"] = 1
ans = 1

For the single character word "s", there is no reverse in cnt. No pair is formed.

cnt["s"] = 1
ans = 1

The last word is "sssll". Its reverse "llsss" is not in cnt, so no final pair is formed.

cnt["llsss"] = 1
ans = 1

After iterating through the array, we find that the maximum number of unique pairs that can be formed is 1, with the paired words being "abcd" and "dcba". The other words did not pair with any other words, either because their reverses weren't present or because each string can be part of at most one pair. Thus, ans = 1 is returned as the final output of the algorithm.

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
6        # Initialize a counter to keep track of palindrome pairs
7        palindrome_pairs_counter = Counter()
8      
9        # Initialize a variable to count the number of palindrome pairs
10        number_of_pairs = 0
11      
12        # Iterate over each word in the input list of words
13        for word in words:
14            # For each word, check if its reverse is already in the counter,
15            # which would make a palindrome pair, and if so, increment the pairs count.
16            number_of_pairs += palindrome_pairs_counter[word]
17          
18            # Increment the counter for the reverse of the current word,
19            # to account for future potential pairs.
20            palindrome_pairs_counter[word[::-1]] += 1
21      
22        # Return the total count of palindrome pairs
23        return number_of_pairs
24

1class Solution {
2  
3    /**
4     * This method calculates the maximum number of string pairs where one string 
5     * is the reverse of the other in a given array of strings.
6     *
7     * @param words An array of strings to find the maximum number of reversible string pairs.
8     * @return The maximum number of reversible string pairs.
9     */
10    public int maximumNumberOfStringPairs(String[] words) {
11        // A map to count occurrences of the reversed strings.
12        Map<String, Integer> reverseCountMap = new HashMap<>(words.length);
13      
14        // Counter to keep track of the total number of reversible string pairs.
15        int totalPairs = 0;
16      
17        // Iterate through each word in the array.
18        for (String word : words) {
19            // If the word has appeared as a reverse before, increment the total pairs count by the
20            // number of times the reverse has appeared.
21            totalPairs += reverseCountMap.getOrDefault(word, 0);
22          
23            // Reverse the current word.
24            String reversedWord = new StringBuilder(word).reverse().toString();
25          
26            // Update the reverse count map by incrementing the count of the reverse of the current word.
27            // If this reversed word is not in the map, it's added with a count of 1. If it is already there,
28            // the existing count is incremented by 1.
29            reverseCountMap.merge(reversedWord, 1, Integer::sum);
30        }
31      
32        // Return the computed total number of reversible string pairs.
33        return totalPairs;
34    }
35}
36

1#include <algorithm>
2#include <string>
3#include <unordered_map>
4#include <vector>
5
6class Solution {
7public:
8    // This function computes the maximum number of pairs of strings
9    // where one is the reverse of the other
10    int maximumNumberOfStringPairs(std::vector<std::string>& words) {
11        // Create a hash map to count occurrences of each reversed word
12        std::unordered_map<std::string, int> reverse_word_count;
13        // Initialize count of valid pairs to zero
14        int max_pair_count = 0;
15      
16        // Loop through each word in the vector
17        for (auto& word : words) {
18            // Increment the count of pairs for each word that is a reverse 
19            // of a previously encountered word
20            max_pair_count += reverse_word_count[word];
21          
22            // Reverse the current word in-place
23            std::reverse(word.begin(), word.end());
24
25            // Increment the count of the reversed word in our hash map
26            reverse_word_count[word]++;
27        }
28
29        // Answer is the total count of valid pairs found
30        return max_pair_count;
31    }
32};
33

1function maximumNumberOfStringPairs(words: string[]): number {
2    // Create a map to count the occurrences of each reversed word.
3    const reversedWordCount: Map<string, number> = new Map();
4    let pairCount = 0; // Initialize the count of pairs to 0.
5
6    // Iterate over the array of words.
7    for (const word of words) {
8        // Check if the current word has a reverse counterpart already counted.
9        pairCount += reversedWordCount.get(word) || 0;
10
11        // Find the reversed string of the current word.
12        const reversedWord = word.split('').reverse().join('');
13
14        // Update the count of the reversed word in the map, incrementing the current value or setting to 1 if not present.
15        reversedWordCount.set(reversedWord, (reversedWordCount.get(reversedWord) || 0) + 1);
16    }
17
18    // Return the total number of pairs found.
19    return pairCount;
20}
21

Time and Space Complexity

Time Complexity

The time complexity of the provided code is primarily determined by the loop that iterates through each word in the input list words. The operations within the loop are constant-time lookups and updates to the counter, cnt, which is a hash map. For n words:

The ans += cnt[w] operation is O(1) because it is a hash map lookup.
The cnt[w[::-1]] += 1 operation involves reversing the word which costs O(k) where k is the length of the word, and the hash map update is O(1).

Since the reversal of the word is the most expensive operation within the loop, and it happens for each word, the overall time complexity is O(nk), where n is the number of words and k is the average length of the words.

Space Complexity

The space complexity is determined by the space required to store the counter, cnt. In the worst-case scenario, if all words and their reverses are unique, the counter would need to store an entry for each unique word and its reversed counterpart. Therefore, the space complexity is O(n) where n is the number of unique words in the list.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of these pictures shows the visit order of a depth-first search?

I don’t know