Find Maximum Number of String Pairs - Video Solutions

Problem Overview: You are given an array of two‑character strings. A valid pair exists when one string is the reverse of another string in the array (for example, "ab" and "ba"). The goal is to count the maximum number of such disjoint pairs.

Approach 1: Brute Force Pair Checking (O(n²) time, O(1) space)

The direct method compares every string with every other string. Iterate through the array using two nested loops. For each string words[i], compute its reverse and check if it matches any words[j] where j > i. If a match is found, count the pair and ensure those indices are not reused. This approach relies only on basic iteration and string comparison, making it useful for understanding the core requirement of the problem. However, because it performs pairwise comparisons across the array, the time complexity grows quadratically as the input size increases.

Even though the brute force method works within constraints for small inputs, it becomes inefficient when the number of strings increases. The algorithm performs repeated reverse checks and comparisons, which makes it a good baseline but not the best choice when an optimized lookup structure is available.

Approach 2: Hash Map for Quick Lookups (O(n) time, O(n) space)

A more efficient solution uses a hash-based structure to track strings you've already seen. Iterate through the array once. For each string, compute its reversed form (for example, "ab" → "ba"). Before storing the current string, check whether the reversed string already exists in the hash map or hash set. If it does, you found a valid pair, so increment the pair count and remove the stored string to avoid reuse.

This works because a hash lookup runs in constant time on average. Instead of comparing against every other element, you immediately determine whether the complementary reversed string exists. Each string is processed once, making the total runtime linear relative to the number of elements.

The approach is a common pattern in problems involving complements or reverse matching. The hash structure acts as a memory of previously seen elements and eliminates redundant comparisons. Problems involving string transformations often combine hash table lookups with simple string operations while iterating through an array.

Recommended for interviews: Start by explaining the brute force method to demonstrate that you understand the definition of a valid pair. Then move to the hash map approach, which reduces the runtime from quadratic to linear. Interviewers usually expect the hash-based solution because it shows awareness of efficient lookups and common optimization patterns.