Two-Letter Card Game - Solution & Explanation

Problem Overview: You are given a list of cards where each card contains a string of exactly two lowercase letters. The task is to determine how many valid plays (pairs or combinations) can be formed based on relationships between the two-letter strings. The core challenge is efficiently identifying complementary cards such as reversed pairs while avoiding double counting.

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

The most direct approach compares every card with every other card. For each pair of indices i and j, check whether the two cards form a valid play according to the game rule (for example, matching a string with its reversed form). This requires a nested loop over the array and explicit string comparison. While simple to implement and useful for verifying correctness on small inputs, the quadratic runtime becomes impractical when the number of cards grows large.

Approach 2: Hash Table Counting (O(n) time, O(n) space)

A more efficient strategy counts occurrences of each two-letter string using a hash map. As you iterate through the cards, compute the reversed version of the current card (e.g., "ab" → "ba"). If the reversed card already exists in the map with unused frequency, you can immediately form a valid pair and decrement the stored count. Otherwise, store the current card in the map for future matches. This technique relies on constant-time hash lookups and ensures each card is processed exactly once.

Special attention is required for symmetric cards like "aa", where the reversed string is identical. Instead of matching with a different string key, you pair them within the same frequency bucket by counting how many identical cards appear and forming pairs accordingly. This is a classic frequency-counting pattern commonly used in hash table and counting problems involving small strings.

The algorithm scans the input once, performs constant-time hash lookups, and tracks counts of unmatched cards. This reduces the complexity to linear time while using extra space proportional to the number of unique strings. The technique is widely used for problems involving reverse matching in string processing tasks.

Recommended for interviews: Interviewers expect the hash-table counting approach. Demonstrating the brute-force solution first shows you understand the pairing requirement, but the optimized O(n) solution proves you can recognize reverse relationships and apply frequency maps to eliminate redundant comparisons.