Game of Master Mind

Problem

The Game of Master Mind is played as follows. The computer chooses a code consisting of four colors from {R, Y, G, B}. A player makes a guess (also four colors). For each guess the player is told:

• hits (correct color in correct position), and
• pseudo-hits (correct color in wrong position).

Examples

Example 1

Input: solution = RGGB, guess = YRGB
Output: (2, 1)
Explanation: 
SOLUTION: R G G B
GUESS:    Y R G B
POSITION: 1 2 3 4
Hits are 2 at positions 3 and 4, and pseudo-hits: 1 (color R exists but in wrong position)

Return the number of hits and pseudo-hits for a given guess and solution.

Note: LeetCode has a very similar problem [Bulls and Cows](bulls-and-cows).

Solution

We provide two clean approaches: Method 1 uses frequency counts (recommended), Method 2 uses a compact bit-mask idea for small alphabets.

Method 1 — Two-Pass Frequency Counts (Recommended)

Intuition

Count exact matches (hits) in one pass. For non-matching positions, count remaining colors in the solution and then match them against the guess to compute pseudo-hits.

Approach

• Initialize hits = 0, pseudo = 0 and an array cnt[4] for colors {R,Y,G,B}.
• First pass: for each index i, if guess[i] == solution[i] increment hits; else increment cnt[index_of(solution[i])].
• Second pass: for each index i where guess[i] != solution[i], if cnt[index_of(guess[i])] > 0 then increment pseudo and decrement that count.
• Return (hits, pseudo).

Code

C++

class Solution {
 public:
  std::pair<int, int> masterMind(const std::string& guess, const std::string& solution) {
    auto idx = [](char c) { return c == 'R' ? 0 : c == 'Y' ? 1 : c == 'G' ? 2 : 3; };
    int hits = 0, pseudo = 0;
    int cnt[4] = {0, 0, 0, 0};
    for (size_t i = 0; i < guess.size(); ++i) {
      if (guess[i] == solution[i]) {
        ++hits;
      } else {
        ++cnt[idx(solution[i])];
      }
    }
    for (size_t i = 0; i < guess.size(); ++i) {
      if (guess[i] == solution[i]) continue;
      int j = idx(guess[i]);
      if (cnt[j] > 0) {
        --cnt[j];
        ++pseudo;
      }
    }
    return {hits, pseudo};
  }
};

Go

// masterMind returns (hits, pseudoHits) for the Master Mind guess evaluation.
func masterMind(guess, solution string) (int, int) {
  idx := func(c byte) int {
    switch c {
    case 'R': return 0
    case 'Y': return 1
    case 'G': return 2
    default:  return 3
    }
  }
  hits, pseudo := 0, 0
  var cnt [4]int
  for i := 0; i < len(guess); i++ {
    if guess[i] == solution[i] {
      hits++
    } else {
      cnt[idx(solution[i])]++
    }
  }
  for i := 0; i < len(guess); i++ {
    if guess[i] == solution[i] { continue }
    j := idx(guess[i])
    if cnt[j] > 0 {
      cnt[j]--
      pseudo++
    }
  }
  return hits, pseudo
}

Java

class Solution {
  private int idx(char c) { return c == 'R' ? 0 : c == 'Y' ? 1 : c == 'G' ? 2 : 3; }

  static class Result { int hits; int pseudoHits; }

  public Result masterMind(String guess, String solution) {
    Result res = new Result();
    int[] cnt = new int[4];
    for (int i = 0; i < guess.length(); i++) {
      if (guess.charAt(i) == solution.charAt(i)) {
        res.hits++;
      } else {
        cnt[idx(solution.charAt(i))]++;
      }
    }
    for (int i = 0; i < guess.length(); i++) {
      if (guess.charAt(i) == solution.charAt(i)) continue;
      int j = idx(guess.charAt(i));
      if (cnt[j] > 0) {
        cnt[j]--;
        res.pseudoHits++;
      }
    }
    return res;
  }
}

Python

class Solution:
  def masterMind(self, guess: str, solution: str) -> tuple[int, int]:
    def idx(c: str) -> int:
      return 0 if c == 'R' else 1 if c == 'Y' else 2 if c == 'G' else 3

    hits = 0
    pseudo = 0
    cnt = [0] * 4
    for i, gch in enumerate(guess):
      if gch == solution[i]:
        hits += 1
      else:
        cnt[idx(solution[i])] += 1
    for i, gch in enumerate(guess):
      if gch == solution[i]:
        continue
      j = idx(gch)
      if cnt[j] > 0:
        cnt[j] -= 1
        pseudo += 1
    return hits, pseudo

Kotlin

class Solution {
  private fun idx(c: Char) = when (c) { 'R' -> 0; 'Y' -> 1; 'G' -> 2; else -> 3 }
  data class Result(var hits: Int = 0, var pseudo: Int = 0)
  fun masterMind(guess: String, solution: String): Result {
    val cnt = IntArray(4)
    val res = Result()
    for (i in guess.indices) {
      if (guess[i] == solution[i]) res.hits++ else cnt[idx(solution[i])]++
    }
    for (i in guess.indices) {
      if (guess[i] == solution[i]) continue
      val j = idx(guess[i])
      if (cnt[j] > 0) { cnt[j]--; res.pseudo++ }
    }
    return res
  }
}

Rust

pub struct Solution;

impl Solution {
  pub fn master_mind(guess: &str, solution: &str) -> (i32, i32) {
    fn idx(c: u8) -> usize { match c { b'R' => 0, b'Y' => 1, b'G' => 2, _ => 3 } }
    let g = guess.as_bytes();
    let s = solution.as_bytes();
    let mut hits = 0;
    let mut pseudo = 0;
    let mut cnt = [0i32; 4];
    for i in 0..g.len() {
      if g[i] == s[i] {
        hits += 1;
      } else {
        cnt[idx(s[i])] += 1;
      }
    }
    for i in 0..g.len() {
      if g[i] == s[i] { continue; }
      let j = idx(g[i]);
      if cnt[j] > 0 {
        cnt[j] -= 1;
        pseudo += 1;
      }
    }
    (hits, pseudo)
  }
}

TypeScript

class Solution {
  private idx(c: string): number { return c === 'R' ? 0 : c === 'Y' ? 1 : c === 'G' ? 2 : 3; }
  masterMind(guess: string, solution: string): [number, number] {
    let hits = 0, pseudo = 0;
    const cnt = [0, 0, 0, 0];
    for (let i = 0; i < guess.length; i++) {
      if (guess[i] === solution[i]) {
        hits++;
      } else {
        cnt[this.idx(solution[i])]++;
      }
    }
    for (let i = 0; i < guess.length; i++) {
      if (guess[i] === solution[i]) continue;
      const j = this.idx(guess[i]);
      if (cnt[j] > 0) {
        cnt[j]--;
        pseudo++;
      }
    }
    return [hits, pseudo];
  }
}

Complexity

• ⏰ Time complexity: O(L) where L is the length of the code (here L=4), because we scan the strings twice.
• 🧺 Space complexity: O(1) — constant extra space for counts.

Method 2 — Single-Pass Net Counting (Bit/Count Hybrid)

Intuition

We can compute hits and pseudo-hits in one pass (instead of two) by tracking the net availability of each color. When we encounter a mismatch pair (g,s):

• If we previously saw more of g in solution (net count > 0), then using g now creates a pseudo-hit.
• If we previously saw more of s in guess (net count < 0), then seeing s on solution side completes a pseudo-hit.

This mirrors the well-known single-pass trick used for Bulls & Cows, specialized to 4 colors. We optionally keep a small bit-mask for presence, though the net counts alone suffice and handle duplicates safely.

Approach

• Maintain int net[4] initialized to 0 (color index mapping same as Method 1).
• Iterate positions i:
  • If guess[i] == solution[i]: hits++.
  • Else:
  • g = idx(guess[i]), s = idx(solution[i]).
  • If net[g] > 0 then pseudo++ (solution had surplus of this color earlier).
  • If net[s] < 0 then pseudo++ (guess had surplus of this color earlier).
  • Decrement net[g] (we consumed a guess color) and increment net[s] (we add a solution color).

Code

C++

class Solution {
 public:
  std::pair<int, int> masterMind(const std::string& guess, const std::string& solution) {
    auto idx = [](char c) { return c == 'R' ? 0 : c == 'Y' ? 1 : c == 'G' ? 2 : 3; };
    int hits = 0, pseudo = 0;
    int net[4] = {0, 0, 0, 0};
    for (size_t i = 0; i < guess.size(); ++i) {
      if (guess[i] == solution[i]) { hits++; continue; }
      int g = idx(guess[i]);
      int s = idx(solution[i]);
      if (net[g] > 0) pseudo++;  // solution previously had this color unused
      if (net[s] < 0) pseudo++;  // guess previously had this color unused
      net[g]--; net[s]++;
    }
    return {hits, pseudo};
  }
};

Java

class Solution {
  private int idx(char c) { return c == 'R' ? 0 : c == 'Y' ? 1 : c == 'G' ? 2 : 3; }
  static class Result { int hits; int pseudoHits; }
  public Result masterMind(String guess, String solution) {
    Result res = new Result();
    int[] net = new int[4];
    for (int i = 0; i < guess.length(); i++) {
      char gch = guess.charAt(i), sch = solution.charAt(i);
      if (gch == sch) { res.hits++; continue; }
      int g = idx(gch), s = idx(sch);
      if (net[g] > 0) res.pseudoHits++;
      if (net[s] < 0) res.pseudoHits++;
      net[g]--; net[s]++;
    }
    return res;
  }
}

Python

class Solution:
  def masterMind(self, guess: str, solution: str) -> tuple[int, int]:
    def idx(c: str) -> int:
      return 0 if c == 'R' else 1 if c == 'Y' else 2 if c == 'G' else 3

    net = [0] * 4
    hits = 0
    pseudo = 0
    for gch, sch in zip(guess, solution):
      if gch == sch:
        hits += 1
        continue
      g = idx(gch)
      s = idx(sch)
      if net[g] > 0:
        pseudo += 1
      if net[s] < 0:
        pseudo += 1
      net[g] -= 1
      net[s] += 1
    return hits, pseudo

TypeScript

class Solution {
  private idx(c: string) { return c === 'R' ? 0 : c === 'Y' ? 1 : c === 'G' ? 2 : 3; }
  masterMind(guess: string, solution: string): [number, number] {
    const net = [0, 0, 0, 0];
    let hits = 0, pseudo = 0;
    for (let i = 0; i < guess.length; i++) {
      const g = guess[i], s = solution[i];
      if (g === s) { hits++; continue; }
      const gi = this.idx(g), si = this.idx(s);
      if (net[gi] > 0) pseudo++;
      if (net[si] < 0) pseudo++;
      net[gi]--; net[si]++;
    }
    return [hits, pseudo];
  }
}

Complexity

• ⏰ Time complexity: O(L) – single pass over code length.
• 🧺 Space complexity: O(1) – fixed-size arrays (4 colors).