2744. Find Maximum Number of String Pairs
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.
Which of the following shows the order of node visit in a Breadth-first Search?
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
Counterobject namedcntand a variable namedansset to 0, which will keep track of the total number of pairs found. -
The
forloop iterates through each word in the givenwordsarray. -
Each iteration performs two operations:
- It increments the answer
ansby 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.
- It increments the answer
-
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.
Which of the following uses divide and conquer strategy?
Example Walkthrough
Let's walk through a small example to illustrate the solution approach using the following words array:
1words = ["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.
1cnt = Counter() 2ans = 0
As we iterate through the words array:
- For the first word
"abcd", its reverse is"dcba", which is not yet incnt, so no pair is formed. Updatecntwith the reverse of the current word.
1cnt["dcba"] = 1 2ans = 0
- The next word
"dcba"has a reverse"abcd", which is already incnt. It's a match! Incrementansby 1 and updatecntfor the reverse"badc".
1cnt["badc"] = 1 2ans = 1
- The third word
"lls"does not have its reverse incnt, so no new pair is formed yet.
1cnt["sll"] = 1 2ans = 1
- For the single character word
"s", there is no reverse incnt. No pair is formed.
1cnt["s"] = 1 2ans = 1
- The last word is
"sssll". Its reverse"llsss"is not incnt, so no final pair is formed.
1cnt["llsss"] = 1 2ans = 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
241class 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}
361#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};
331function 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}
21Which of the following problems can be solved with backtracking (select multiple)
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 isO(1)because it is a hash map lookup. - The
cnt[w[::-1]] += 1operation involves reversing the word which costsO(k)wherekis the length of the word, and the hash map update isO(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.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.