We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Maximum Number of String Pairs

Number: 2847

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed array of distinct two-letter strings, determine the maximum number of pairs where one string is the reverse of the other. A pair is valid if for indices i < j, words[i] is equal to the reversed string of words[j]. Each string can be used at most once.

Key Insights

  • Since every word has exactly two characters, reversing it is straightforward.
  • Use a hash set (or dictionary) to record words that have not yet been paired.
  • When processing a word, check if its reverse is already in the set.
  • Once a pair is found, remove the reverse from the set to avoid reuse.
  • Because the array contains distinct words, there is no risk of pairing the same string with itself unless it is palindromic; however, a palindromic string cannot be paired because it appears only once in the array.

Space and Time Complexity

Time Complexity: O(n), where n is the number of words. Space Complexity: O(n), for storing unpaired words in the set.

Solution

We iterate through the list of words and for each word, generate its reversed version. We maintain a set to track words that are waiting to be paired. If the reversed word is found in the set, it means a valid pair exists. We then remove the reversed word from the set and increase the count of pairs. If the reversed word isn’t found, we add the current word to the set to potentially be paired with a future word. This approach ensures each word is processed only once, achieving an optimal solution in linear time.

Code Solutions

# Python solution for finding maximum number of string pairs

def max_pairs(words):
    # Set to track unpaired words
    waiting = set()
    pairs_count = 0
    
    # Iterate over each word in the list
    for word in words:
        # Create the reversed version of the current word
        reversed_word = word[::-1]
        
        # If the reversed word is in waiting, a pair is found
        if reversed_word in waiting:
            # Remove the reversed word from the waiting set,
            # because it is now used in a pair
            waiting.remove(reversed_word)
            # Increment the count of valid pairs
            pairs_count += 1
        else:
            # If not found, add the current word to the waiting set
            waiting.add(word)
    
    # Return the total number of pairs formed
    return pairs_count

# Example usage:
words = ["cd", "ac", "dc", "ca", "zz"]
print(max_pairs(words))  # Output: 2
← Back to All Questions