Two-Letter Card Game solution and explanation
Google
6 more videos on this problem
Biweekly Contest 164 🔥 LeetCode 3664 | Two-Letter Card Game | Full Explanation + Java Solution Study Placement · 21:42 · 864 views
Two-Letter Card Game | Q2 of Biweekly Contest 164ExpertFunda · 13:12 · 765 views
Leetcode 3664 | Two-Letter Card Game | Biweekly contest 164CodeWithMeGuys · 22:17 · 633 views
Leetcode 3664 | Two-Letter Card Game Detailed Solution with Dry Run | Biweekly 164 Q2Samrat Bhardwaj · 48:32 · 527 views
3664. Two-Letter Card Game (Leetcode Medium)Programming Live with Larry · 43:52 · 440 views
3664. Two-Letter Card Game | Leetcode Weekly Contest 164Break and Build · 33:17 · 200 views
Leetcode Biweekly Contest 164 - Q2. Two-Letter Card GameADevOpsEngineer · 16:29 · 168 views
The problem
You are given a deck of cards represented by a string array cards, and each card displays two lowercase letters.
You are also given a letter x. You play a game with the following rules:
- Start with 0 points.
- On each turn, you must find two compatible cards from the deck that both contain the letter
xin any position. - Remove the pair of cards and earn 1 point.
- The game ends when you can no longer find a pair of compatible cards.
Return the maximum number of points you can gain with optimal play.
Two cards are compatible if the strings differ in exactly 1 position.
Example 1:
Input: cards = ["aa","ab","ba","ac"], x = "a"
Output: 2
Explanation:
- On the first turn, select and remove cards
"ab"and"ac", which are compatible because they differ at only index 1. - On the second turn, select and remove cards
"aa"and"ba", which are compatible because they differ at only index 0.
Because there are no more compatible pairs, the total score is 2.
Example 2:
Input: cards = ["aa","ab","ba"], x = "a"
Output: 1
Explanation:
- On the first turn, select and remove cards
"aa"and"ba".
Because there are no more compatible pairs, the total score is 1.
Example 3:
Input: cards = ["aa","ab","ba","ac"], x = "b"
Output: 0
Explanation:
The only cards that contain the character 'b' are "ab" and "ba". However, they differ in both indices, so they are not compatible. Thus, the output is 0.
Constraints:
2 <= cards.length <= 105cards[i].length == 2- Each
cards[i]is composed of only lowercase English letters between'a'and'j'. xis a lowercase English letter between'a'and'j'.
Approach overview
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(n2) 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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Small inputs or when first reasoning about the pairing rule |
| Hash Table Counting | O(n) | O(n) | General case; optimal approach using frequency map and reverse lookup |
Frequently asked questions
Is Two-Letter Card Game easy or hard?
Two-Letter Card Game is considered a Medium difficulty problem. The logic is straightforward once you recognize the reverse-pair pattern, but many candidates initially attempt a quadratic brute-force comparison before realizing a hash table reduces the complexity to O(n).
Two-Letter Card Game Python/Java solution
In Python, a dictionary or collections.Counter can track frequencies while iterating through the cards. In Java, HashMap<String, Integer> is commonly used to store counts and check reversed strings. The same logic translates directly to C++ using unordered_map and to Go using a map[string]int.
How to solve Two-Letter Card Game in O(n)?
Iterate through the list of two-letter strings and maintain a hash map of unmatched cards. For each card, compute its reversed string and check if that reverse already exists in the map. If it does, create a valid pair and decrement the stored count; otherwise store the current card. This avoids nested comparisons and keeps the algorithm linear.
What is the best approach for Two-Letter Card Game?
The optimal solution uses a hash table to count occurrences of each two-letter card and match it with its reversed string. While iterating through the array, check whether the reverse of the current card already exists in the map. If it does, form a pair and reduce the stored frequency. This approach runs in O(n) time with O(n) additional space.
Is Two-Letter Card Game asked at Google/Amazon/Meta?
Problems involving reverse string pairing and frequency counting appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. Variants that require pairing strings, building palindromes, or matching reversed patterns are common interview exercises.
What data structure is used in Two-Letter Card Game?
The primary data structure is a hash table (hash map) that stores the frequency of each two-letter string. This allows constant-time lookups when checking whether the reversed version of a card already exists. Arrays or dictionaries are typically used depending on the programming language.
What is the time complexity of Two-Letter Card Game?
The optimal hash-table approach runs in O(n) time because each card is processed once and each lookup in the map takes constant time on average. Space complexity is O(n) in the worst case when all cards are unique and must be stored in the frequency map.