Two letter card game

Array Hash Table String Counting Enumeration

12.2% acceptance

Feb 25, 2026

119

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn score(cards: Vec<String>, x: char) -> i32 {
    // Category XA: "xa" where a != x; AX: "ax" where a != x; XX: "xx"
    let mut xa_cnt = [0usize; 26];
    let mut ax_cnt = [0usize; 26];
    let mut xx_cnt = 0usize;
    let xi = (x as u8 - b'a') as usize;

    for card in &cards {
      let b = card.as_bytes();
      let c0 = (b[0] - b'a') as usize;
      let c1 = (b[1] - b'a') as usize;
      if c0 == xi && c1 == xi { xx_cnt += 1; }
      else if c0 == xi { xa_cnt[c1] += 1; }
      else if c1 == xi { ax_cnt[c0] += 1; }
    }

    let xa_groups: Vec<usize> = xa_cnt.iter().filter(|&&c| c > 0).cloned().collect();
    let ax_groups: Vec<usize> = ax_cnt.iter().filter(|&&c| c > 0).cloned().collect();
    let n_xa: usize = xa_groups.iter().sum();
    let n_ax: usize = ax_groups.iter().sum();

    // f(groups, k) = k C-A wildcard pairs + max AA pairs from remaining after removing k optimally
    let compute_f = |groups: &[usize], k: usize| -> usize {
      let n: usize = groups.iter().sum();
      let k = k.min(n);
      if k == n { return n; }
      let remaining = n - k;
      // Binary search for minimum achievable max_c after removing k items
      let max_val = groups.iter().max().cloned().unwrap_or(0);
      let mut lo = 0usize;
      let mut hi = max_val;
      while lo < hi {
        let mid = (lo + hi) / 2;
        let to_remove: usize = groups.iter().map(|&g| g.saturating_sub(mid)).sum();
        if to_remove <= k { hi = mid; } else { lo = mid + 1; }
      }
      let max_c = lo;
      let aa = if max_c >= remaining { 0 }
           else if max_c > remaining - max_c { remaining - max_c }
           else { remaining / 2 };
      k + aa
    };

    let mut best = 0;
    let k_max = xx_cnt.min(n_xa);
    for k_a in 0..=k_max {
      let k_b = (xx_cnt - k_a).min(n_ax);
      let s = compute_f(&xa_groups, k_a) + compute_f(&ax_groups, k_b);
      best = best.max(s);
    }
    best as i32
  }
}