Find Maximum Number of String Pairs

There are 676 possible 2-character strings.

So, we can use a boolean array to track if we’ve seen a string before.

Let’s break down the explanation in simpler terms and discuss how we can utilize a boolean array to solve this problem.

  1. Understanding 2-Character Strings: Since the strings contain only 2 characters and are composed of lowercase English letters, there are a total of 26 * 26 = 676 possible 2-character strings. Think of it like a 26x26 grid, where each cell represents a unique combination of two letters.

  2. Creating a Boolean Array: We can use a boolean array of size 676 to track if we have seen a particular 2-character string before. Each element in the array will correspond to one unique 2-character string. Initially, all elements will be set to False, meaning we haven’t seen any strings yet.

  3. Mapping Strings to Array Index: We need a way to map each 2-character string to a unique index in the boolean array. We can do this by converting the characters into their corresponding ASCII values and calculating the index as index = (first_character - 'a') * 26 + (second_character - 'a').

  4. Tracking Reversed Strings: As we go through the given list of words, for each word, we’ll check if the reversed version of that word has been seen before by checking the corresponding index in the boolean array. If it has been seen, we can form a pair.

  5. Updating the Array: After checking, we’ll update the boolean array for the current word, marking that we’ve seen this word.

  6. Counting Pairs: We’ll keep track of the number of pairs we’ve found and return that as the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def maximumNumberOfStringPairs(self, words: List[str]) -> int:
        # Initialize a boolean array of size 676
        seen = [False] * 676

        # Initialize variable to store the number of pairs
        pairs = 0

        # Iterate through the words
        for word in words:
            # Calculate the index for the reversed word
            index = (ord(word[1]) - ord('a')) * 26 + (ord(word[0]) - ord('a'))

            # Check if the reversed word has been seen before
            if seen[index]:
                pairs += 1

            # Mark the current word as seen
            seen[(ord(word[0]) - ord('a')) * 26 + (ord(word[1]) - ord('a'))] = True

        # Return the result
        return pairs

Key Takeaways

  • By using a boolean array, we are efficiently tracking the existence of 2-character strings.
  • This method helps us quickly identify pairs where one string is the reverse of the other.
  • The solution is simple and direct, utilizing the fact that there are only 676 possible 2-character strings.