Find Maximum Number of String Pairs

Easy

Asked by:

15 views

Topics:

ArraysStringsTwo Pointers

You are given a 0-indexed array words consisting of distinct strings.

The string words[i] can be paired with the string words[j] if:

The string words[i] is equal to the reversed string of words[j].
0 <= i < j < words.length.

Return the maximum number of pairs that can be formed from the array words.

Note that each string can belong in at most one pair.

Example 1:

Input: words = ["cd","ac","dc","ca","zz"]
Output: 2
Explanation: In this example, we can form 2 pair of strings in the following way:
- We pair the 0^th string with the 2^nd string, as the reversed string of word[0] is "dc" and is equal to words[2].
- We pair the 1^st string with the 3^rd string, as the reversed string of word[1] is "ca" and is equal to words[3].
It can be proven that 2 is the maximum number of pairs that can be formed.

Example 2:

Input: words = ["ab","ba","cc"]
Output: 1
Explanation: In this example, we can form 1 pair of strings in the following way:
- We pair the 0^th string with the 1^st string, as the reversed string of words[1] is "ab" and is equal to words[0].
It can be proven that 1 is the maximum number of pairs that can be formed.

Example 3:

Input: words = ["aa","ab"]
Output: 0
Explanation: In this example, we are unable to form any pair of strings.

Constraints:

1 <= words.length <= 50
words[i].length == 2
words consists of distinct strings.
words[i] contains only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input `words` array, and the maximum length of each individual word string?
Are the words case-sensitive? For example, should "ab" and "Ba" be considered a pair?
If no pairs exist, what should I return? Should I return 0, or is there another specific value?
Can the input array contain duplicate words? If so, how should they be handled?
Is an empty string considered a valid word in the input array?

Brute Force Solution

Approach

The goal is to find pairs of words in a list where one word is the reverse of the other. We will simply check every possible pair of words to see if they are reverses of each other.

Here's how the algorithm would work step-by-step:

Take the first word in the list.
Compare it to every other word in the list to see if it is the reverse of the other word.
If you find a reversed pair, mark them as counted so you don't count them again.
Move on to the next word in the list.
Again, compare it to every other word in the list (that hasn't already been counted) to see if it has a reverse.
Keep doing this for every word in the list.
Count up the number of reversed pairs you found.

Code Implementation

def find_maximum_number_of_string_pairs(words):
    number_of_words = len(words)
    pairs_found = 0
    counted = [False] * number_of_words

    for first_word_index in range(number_of_words):
        # Only process the word if it hasn't been counted already
        if not counted[first_word_index]:

            for second_word_index in range(first_word_index + 1, number_of_words):
                # Check if the other word is a reverse and hasn't been counted
                if not counted[second_word_index] and words[first_word_index] == words[second_word_index][::-1]:
                    pairs_found += 1

                    # Mark both words as counted to avoid double-counting
                    counted[first_word_index] = True

                    counted[second_word_index] = True

                    # No need to check other words after a pair is found
                    break

    return pairs_found

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n words in the input list. For each word, it compares it with every other word in the list that hasn't been previously counted as part of a pair. In the worst case, this involves checking close to n words for each of the n words in the input. Thus, the total number of comparisons approximates to n * n/2, which simplifies to O(n²).

Space Complexity

O(N) – The provided algorithm requires a way to track which words have already been counted in a pair to avoid double-counting. This can be implemented using a boolean array or a set of size N, where N is the number of words in the input list, to mark visited words. Therefore, the auxiliary space needed to keep track of the counted pairs grows linearly with the number of words in the input list. Thus, the space complexity is O(N).

Optimal Solution

Approach

The most efficient way to find string pairs involves checking if each word has a reverse counterpart. We avoid unnecessary comparisons by storing words in a way that allows quick lookups for their reversed forms. By finding pairs, we avoid checking every possible combination.

Here's how the algorithm would work step-by-step:

Start by creating a way to keep track of the words we've seen so far. A collection works well for this.
Go through each word in the given list.
For each word, create its reversed version.
Check if the reversed version is already in our collection of seen words. If it is, we've found a pair. Increase our pair count.
If we found a pair, remove the reversed word from the collection to avoid double-counting pairs.
If the reversed word isn't in our collection, add the original word to the collection of seen words.
Continue this process for every word in the original list.
The final pair count represents the maximum number of string pairs.

Code Implementation

def find_maximum_number_of_string_pairs(words):
    seen_words = set()
    pair_count = 0

    for word in words:
        reversed_word = word[::-1]

        # Check if the reversed word is already in seen_words.
        if reversed_word in seen_words:
            pair_count += 1

            # Remove the reversed word to avoid double-counting.
            seen_words.remove(reversed_word)

        # Add the original word to seen_words.
        else:
            seen_words.add(word)

    return pair_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n words in the input list. Inside the loop, reversing a word takes constant time because the word length is fixed. Checking for the reversed word in the collection (assuming a hash set or similar data structure) takes O(1) on average. Adding the original word to the collection also takes O(1). Therefore, the dominant operation is the single loop iterating through the input list. This makes the overall time complexity O(n).

Space Complexity

O(N) – The auxiliary space complexity is determined by the collection used to keep track of seen words. In the worst-case scenario, where no word has a reverse counterpart in the input list, the collection will store all N words from the input. Therefore, the space used by the collection scales linearly with the number of words in the input, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no pairs can be formed from an empty input.
Input array with only one string	Return 0, as a pair requires at least two strings.
Input array with strings of different lengths	Only strings of the same length can potentially form a pair when reversed; the comparison should handle this implicitly.
Input array with very long strings (potential performance issue)	Consider optimizing string reversal using efficient algorithms or data structures if the string length becomes a performance bottleneck, though generally a hashmap handles it reasonably well.
Input array where all strings are identical	The algorithm should not count the same string paired with itself and handle duplicates correctly to avoid overcounting.
Input array contains empty strings	An empty string can pair with another empty string and should be handled as a valid (albeit potentially unexpected) case.
Input array with no pairs	The algorithm should correctly return 0 when no pairs exist, demonstrating it doesn't always find a solution.
Input with strings that are palindromes	Palindrome should not be matched with itself unless there are duplicates of that palindrome.

Null or empty input array

How to Handle:

Return 0 immediately, as no pairs can be formed from an empty input.

Input array with only one string

How to Handle:

Return 0, as a pair requires at least two strings.

Input array with strings of different lengths

How to Handle:

Only strings of the same length can potentially form a pair when reversed; the comparison should handle this implicitly.

Input array with very long strings (potential performance issue)

How to Handle:

Consider optimizing string reversal using efficient algorithms or data structures if the string length becomes a performance bottleneck, though generally a hashmap handles it reasonably well.

Input array where all strings are identical

How to Handle:

The algorithm should not count the same string paired with itself and handle duplicates correctly to avoid overcounting.

Input array contains empty strings

How to Handle:

An empty string can pair with another empty string and should be handled as a valid (albeit potentially unexpected) case.

Input array with no pairs

How to Handle:

The algorithm should correctly return 0 when no pairs exist, demonstrating it doesn't always find a solution.

Input with strings that are palindromes

How to Handle:

Palindrome should not be matched with itself unless there are duplicates of that palindrome.