LeetCode 3664 - Two-Letter Card Game

LeetCode Problem 3664

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Counting, Enumeration

Solution

Problem Understanding

Each card consists of exactly two lowercase letters. A card is only relevant if it contains the given letter x somewhere in its two positions.

During the game, we repeatedly select two cards that satisfy two conditions:

1. Both cards contain the letter x.
2. The two strings differ in exactly one position.

After selecting such a pair, both cards are removed and we gain one point.

The goal is to maximize the total number of points.

Since every card has length exactly two, compatibility is very restrictive. Two cards are compatible if they share one position and differ in the other. For example:

• "ab" and "ac" are compatible because only the second character differs.
• "aa" and "ba" are compatible because only the first character differs.
• "ab" and "ba" are not compatible because both positions differ.

The input size can be as large as 100000 cards, so any solution that tries to explicitly search for pairs among cards is far too slow.

An important observation comes from the constraint that every character is between 'a' and 'j'. Since there are only 10 possible letters and every card has length 2, there are only:

$$10 \times 10 = 100$$

possible card types.

This means that although there may be up to 100000 cards, the number of distinct card patterns is tiny.

Important Edge Cases

A naive implementation can easily mishandle several situations.

If no card contains x, the answer is obviously 0.

If only one card contains x, no pair can be formed.

If all relevant cards are identical, no pair can be formed because identical cards differ in zero positions.

If many copies of "xx" exist, they may be paired with cards from either side of the compatibility graph, and choosing those pairings optimally is the key challenge.

Approaches

Brute Force

A straightforward idea is to repeatedly search for two compatible cards containing x, remove them, and continue.

One implementation would examine every pair of remaining cards, find a compatible pair, remove it, and repeat until no more pairs exist.

This approach is correct because it explicitly simulates the game. However, it is completely infeasible.

With up to 100000 cards, even checking all pairs once requires:

$$O(n^2)$$

operations, which is far beyond the allowed limits.

Key Insight

Only cards containing x matter.

Because cards have length 2, every relevant card must be one of the following forms:

• (x, a)
• (a, x)

for some letter a.

There are only 19 such card types:

• "xx"
• "xa" for the other 9 letters
• "ax" for the other 9 letters

Let:

• A = cards of the form "x?"
• B = cards of the form "?x"
• "xx" belongs to both groups

Inside group A, every two different card types are compatible.

Inside group B, every two different card types are compatible.

The only compatibility between the two groups occurs through "xx".

This dramatically reduces the problem. Instead of dealing with up to 100000 cards individually, we only need to count how many copies of each of the 19 relevant card types exist.

The remaining optimization becomes a one-dimensional problem involving how many "xx" cards remain unused by cross-group pairings.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) or worse	O(n)	Explicitly searches for removable pairs
Optimal	O(n)	O(1)	Counts card types and optimizes over a constant-sized state space

Algorithm Walkthrough

Step 1

Count every card type that contains the character x.

For cards of the form "x?" (excluding "xx"), store their frequencies in group A.

For cards of the form "?x" (excluding "xx"), store their frequencies in group B.

Store the frequency of "xx" separately.

Step 2

For each group, compute:

• S = total number of cards in the group
• M = largest frequency among its card types

For a complete compatibility clique, the maximum number of pairs obtainable from counts with an additional r copies of "xx" is:

$$f(S,M,r) = \min\left( \left\lfloor\frac{S+r}{2}\right\rfloor, (S+r)-\max(M,r) \right)$$

The first term comes from the fact that every pair consumes two cards.

The second term comes from the fact that no pair may use two copies of the same card type.

Step 3

Suppose exactly r copies of "xx" remain after cross-group pairings.

Then:

• c - r copies of "xx" were used in cross-group pairings
• each such usage directly contributes one point

The total score becomes:

$$(c-r) + f_A(r) + f_B(r)$$

where c is the total count of "xx" cards.

Step 4

The feasible range of r is:

$$\max(0, c-(S_A+S_B)) \le r \le c$$

because at most S_A + S_B copies of "xx" can participate in cross-group pairings.

Step 5

The function above is piecewise linear with only a constant number of breakpoints.

For each group, breakpoints occur at:

$$2M-S+1$$

and

$$S$$

Combining both groups yields only a constant number of intervals.

Within one interval, the score is linear on each parity of r, therefore the maximum must occur at an interval boundary.

We evaluate only a constant-sized set of candidate values near all interval boundaries and take the maximum score.

Why it works

The entire compatibility structure collapses into two cliques connected only through "xx" cards.

Once the number of remaining "xx" cards is fixed, the optimal score inside each clique is determined uniquely by the formula for maximum pairing in a complete compatibility graph.

Therefore the problem reduces to optimizing a single variable r, and the score function has only a constant number of structural changes. Evaluating all boundary candidates guarantees that the global optimum is found.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def score(self, cards: List[str], x: str) -> int:
        cnt = Counter(cards)

        xx = x + x
        center = cnt[xx]

        a_counts = []
        b_counts = []

        for ch in "abcdefghij":
            if ch == x:
                continue

            a_counts.append(cnt[x + ch])
            b_counts.append(cnt[ch + x])

        sa = sum(a_counts)
        sb = sum(b_counts)

        ma = max(a_counts, default=0)
        mb = max(b_counts, default=0)

        def clique_pairs(S: int, M: int, r: int) -> int:
            total = S + r
            return min(total // 2, total - max(M, r))

        low = max(0, center - (sa + sb))

        boundaries = {
            low,
            center + 1,
            2 * ma - sa + 1,
            sa,
            2 * mb - sb + 1,
            sb,
        }

        points = set()

        sorted_bounds = sorted(boundaries)

        for i in range(len(sorted_bounds) - 1):
            left = max(low, sorted_bounds[i])
            right = min(center, sorted_bounds[i + 1] - 1)

            if left > right:
                continue

            for r in (left, left + 1, right - 1, right):
                if left <= r <= right:
                    points.add(r)

        best = 0

        for r in points:
            score = (
                (center - r)
                + clique_pairs(sa, ma, r)
                + clique_pairs(sb, mb, r)
            )
            best = max(best, score)

        return best

Implementation Explanation

The first part counts all card types. Only cards containing x are relevant.

The frequencies are split into three categories:

• "xx"
• "x?"
• "?x"

The helper function clique_pairs() computes the maximum number of compatible pairs obtainable inside one clique when r copies of "xx" belong to that clique.

The optimization variable is r, the number of "xx" cards not used in cross-group pairings.

Instead of checking every possible r, we exploit the fact that the score function changes behavior only at a constant number of breakpoints. We enumerate interval boundaries, evaluate the score near each boundary, and keep the maximum.

Since the number of card types is fixed, all computations after counting are constant time.

Go Solution

package main

func score(cards []string, x byte) int {
	cnt := make(map[string]int)

	for _, card := range cards {
		cnt[card]++
	}

	xx := string([]byte{x, x})
	center := cnt[xx]

	aCounts := make([]int, 0, 9)
	bCounts := make([]int, 0, 9)

	for ch := byte('a'); ch <= 'j'; ch++ {
		if ch == x {
			continue
		}

		aCounts = append(aCounts, cnt[string([]byte{x, ch})])
		bCounts = append(bCounts, cnt[string([]byte{ch, x})])
	}

	sa, sb := 0, 0
	ma, mb := 0, 0

	for _, v := range aCounts {
		sa += v
		if v > ma {
			ma = v
		}
	}

	for _, v := range bCounts {
		sb += v
		if v > mb {
			mb = v
		}
	}

	cliquePairs := func(S, M, r int) int {
		total := S + r

		a := total / 2
		b := total - max(M, r)

		if a < b {
			return a
		}
		return b
	}

	low := max(0, center-(sa+sb))

	boundaries := map[int]struct{}{
		low:             {},
		center + 1:      {},
		2*ma - sa + 1:   {},
		sa:              {},
		2*mb - sb + 1:   {},
		sb:              {},
	}

	var bounds []int
	for v := range boundaries {
		bounds = append(bounds, v)
	}

	for i := 0; i < len(bounds); i++ {
		for j := i + 1; j < len(bounds); j++ {
			if bounds[j] < bounds[i] {
				bounds[i], bounds[j] = bounds[j], bounds[i]
			}
		}
	}

	points := make(map[int]struct{})

	for i := 0; i+1 < len(bounds); i++ {
		left := max(low, bounds[i])
		right := min(center, bounds[i+1]-1)

		if left > right {
			continue
		}

		candidates := []int{left, left + 1, right - 1, right}

		for _, r := range candidates {
			if r >= left && r <= right {
				points[r] = struct{}{}
			}
		}
	}

	best := 0

	for r := range points {
		cur := (center - r) +
			cliquePairs(sa, ma, r) +
			cliquePairs(sb, mb, r)

		if cur > best {
			best = cur
		}
	}

	return best
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Go-Specific Notes

The Go solution follows exactly the same logic as the Python version.

A map[string]int is used for frequency counting. Since there are only 100 possible card types, memory usage remains constant.

All arithmetic fits comfortably within Go's int type because the answer can never exceed cards.length / 2.

Worked Examples

Example 1

Input:

cards = ["aa","ab","ba","ac"]
x = "a"

Frequency summary:

Type	Count
aa	1
ab	1
ac	1
ba	1

Values:

Variable	Value
center ("aa")	1
SA	2
SB	1
MA	1
MB	1

Try r = 0:

• cross pairs = 1
• clique A contributes 1
• clique B contributes 0

Total:

1 + 1 + 0 = 2

Answer:

2

Example 2

Input:

cards = ["aa","ab","ba"]
x = "a"

Counts:

Type	Count
aa	1
ab	1
ba	1

Values:

Variable	Value
center	1
SA	1
SB	1

Using the single "aa" as a cross-group pairing yields:

1 point

No additional pairs remain.

Answer:

1

Example 3

Input:

cards = ["aa","ab","ba","ac"]
x = "b"

Relevant cards:

Type	Count
ab	1
ba	1

These two cards differ in both positions.

No compatible pair exists.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count card frequencies
Space	O(1)	At most 100 distinct card types

The counting phase dominates the runtime. After counting, only a constant number of card types and candidate states are examined, so the remaining work is constant.

Test Cases

sol = Solution()

assert sol.score(["aa", "ab", "ba", "ac"], "a") == 2  # Example 1
assert sol.score(["aa", "ab", "ba"], "a") == 1        # Example 2
assert sol.score(["aa", "ab", "ba", "ac"], "b") == 0  # Example 3

assert sol.score(["aa", "aa"], "a") == 0              # identical cards only
assert sol.score(["ab", "ac"], "a") == 1              # direct compatible pair
assert sol.score(["ab", "ba"], "a") == 0              # differ in two positions

assert sol.score(["aa", "ab", "ac"], "a") == 1        # one center card helps pairing
assert sol.score(["aa", "aa", "ab", "ba"], "a") == 2  # multiple uses of center cards

assert sol.score(["bc", "cd"], "a") == 0              # no relevant cards
assert sol.score(["ab"], "a") == 0                    # single relevant card

assert sol.score(
    ["aa"] * 50000 + ["ab"] * 25000 + ["ba"] * 25000,
    "a"
) == 50000                                            # large stress case

Test Summary

Test	Why
Example 1	Basic optimal pairing
Example 2	One removable pair
Example 3	Relevant cards exist but are incompatible
["aa","aa"]	Identical cards cannot pair
["ab","ac"]	Simple compatible pair
["ab","ba"]	Differ in both positions
["aa","ab","ac"]	Center card participates strategically
Multiple "aa" cards	Tests cross-group usage
No relevant cards	Answer should be zero
Single relevant card	Cannot form a pair
Large stress case	Validates scalability

Edge Cases

All Relevant Cards Are Identical

Consider:

["aa", "aa", "aa"]

Every card is the same. Compatibility requires differing in exactly one position, but identical cards differ in zero positions. A buggy solution might incorrectly pair equal cards simply because they contain x.

The implementation avoids this because the clique formula never pairs cards of the same type together.

No Card Contains x

Consider:

cards = ["bc", "cd", "de"]
x = "a"

There are no usable cards at all. The answer must be zero.

The counting phase naturally produces zero frequencies for every relevant type, and the optimization returns zero.

Large Number of "xx" Cards

Consider:

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

The "aa" cards can interact with both sides of the compatibility structure. Greedily assigning them to one side may lose optimal pairings.

The solution explicitly models how many "xx" cards remain after cross-group usage and optimizes over all structurally distinct possibilities, guaranteeing the maximum score.

One Dominant Card Type

Consider:

["ab", "ab", "ab", "ab", "ac"]

Although there are five cards, only one pair can be formed because compatible pairs must involve different card types.

The clique formula correctly captures this limitation through the term:

$$(S+r)-\max(M,r)$$

which prevents overcounting when one type dominates the frequency distribution.