LeetCode #3664 — MEDIUM

Two-Letter Card Game

Move from brute-force thinking to an efficient approach using array strategy.

Solve on LeetCode
The Problem

Problem Statement

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 x in 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 <= 105
  • cards[i].length == 2
  • Each cards[i] is composed of only lowercase English letters between 'a' and 'j'.
  • x is a lowercase English letter between 'a' and 'j'.

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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 x in 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Hash Map

Example 1

["aa","ab","ba","ac"]
"a"

Example 2

["aa","ab","ba"]
"a"

Example 3

["aa","ab","ba","ac"]
"b"
Step 02

Core Insight

What unlocks the optimal approach

  • Compute <code>both</code>, <code>cnt1</code>[c], <code>cnt2</code>[c] as the counts of cards with <code>x</code> in both positions, only the first position (other letter <code>c</code>), and only the second position.
  • Let <code>solve(cnt, have)</code> be the maximum pairs you can form from one‐sided counts <code>cnt</code> plus <code>have</code> two‐sided cards by sorting <code>cnt</code>, computing the total, and applying the same logic as in the solution.
  • Return the maximum over <code>i = 0..both</code> of <code>solve(cnt1, i) + solve(cnt2, both - i)</code>.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Upper-end input sizes
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3664: Two-Letter Card Game
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3664: Two-Letter Card Game
// package main
// 
// // https://space.bilibili.com/206214
// // 计算这一组的得分（配对个数），以及剩余元素个数
// func calc(cnt []int, x byte) (int, int) {
// 	sum, mx := 0, 0
// 	for i, c := range cnt {
// 		if i != int(x-'a') {
// 			sum += c
// 			mx = max(mx, c)
// 		}
// 	}
// 	pairs := min(sum/2, sum-mx)
// 	return pairs, sum - pairs*2
// }
// 
// func score(cards []string, x byte) int {
// 	var cnt1, cnt2 [10]int
// 	for _, s := range cards {
// 		if s[0] == x {
// 			cnt1[s[1]-'a']++
// 		} else if s[1] == x {
// 			cnt2[s[0]-'a']++
// 		}
// 	}
// 
// 	pairs1, left1 := calc(cnt1[:], x)
// 	pairs2, left2 := calc(cnt2[:], x)
// 	ans := pairs1 + pairs2 // 不考虑 xx 时的得分
// 
// 	cntXX := cnt1[x-'a']
// 	// 把 xx 和剩下的 x? 和 ?x 配对
// 	// 每有 1 个 xx，得分就能增加一，但这不能超过剩下的 x? 和 ?x 的个数 left1+left2
// 	if cntXX > 0 {
// 		mn := min(cntXX, left1+left2)
// 		ans += mn
// 		cntXX -= mn
// 	}
// 
// 	// 如果还有 xx，就撤销之前的配对，比如 (ax,bx) 改成 (ax,xx) 和 (bx,xx)
// 	// 每有 2 个 xx，得分就能增加一，但这不能超过之前的配对个数 pairs1+pairs2
// 	// 由于这种方案平均每个 xx 只能增加 0.5 分，不如上面的，所以先考虑把 xx 和剩下的 x? 和 ?x 配对，再考虑撤销之前的配对
// 	if cntXX > 0 {
// 		ans += min(cntXX/2, pairs1+pairs2)
// 	}
// 
// 	return ans
// }
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n)
Space
O(1)

Approach Breakdown

BRUTE FORCE
O(n²) time
O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED
O(n) time
O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Related Problems
#1Two Sumeasy→#36Valid Sudokumedium→#41First Missing Positivehard→#73Set Matrix Zeroesmedium→#105Construct Binary Tree from Preorder and Inorder Traversalmedium→