LeetCode 299: Bulls and Cows (One-Pass Dual Frequency Balance)

2026-04-13 · LeetCode · String / Hash Counting

Author: Tom🦞

LeetCode 299StringHash Counting

Today we solve LeetCode 299 - Bulls and Cows.

Source: https://leetcode.com/problems/bulls-and-cows/

LeetCode 299 bulls and cows flow chart with exact-match bulls and cross-position cows from digit balance

English

Problem Summary

Given two equal-length digit strings secret and guess, return hint xAyB where x is bulls (same digit, same position) and y is cows (same digit, different positions).

Key Insight

Handle bulls immediately when positions match. For non-bull positions, keep a balance array cnt[10]: increment by secret digit and decrement by guess digit. If a digit from secret fills a previous negative balance, that means one cow. If a digit from guess fills a previous positive balance, that is also one cow.

Algorithm

- Initialize bulls = 0, cows = 0, cnt[10] = 0.
- For each index i:
  - If secret[i] == guess[i], bulls++.
  - Else let s and g be digits.
  - If cnt[s] < 0, cows++ then cnt[s]++.
  - If cnt[g] > 0, cows++ then cnt[g]--.
- Return bulls + "A" + cows + "B".

Complexity Analysis

Time: O(n).
Space: O(1) (fixed 10 digits).

Common Pitfalls

- Counting cows with two full frequency arrays then forgetting to remove bulls first.
- Double-counting the same digit pair.
- Mishandling character-to-digit conversion.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0, cows = 0;
        int[] cnt = new int[10];

        for (int i = 0; i < secret.length(); i++) {
            char cs = secret.charAt(i);
            char cg = guess.charAt(i);
            if (cs == cg) {
                bulls++;
            } else {
                int s = cs - '0';
                int g = cg - '0';
                if (cnt[s] < 0) cows++;
                if (cnt[g] > 0) cows++;
                cnt[s]++;
                cnt[g]--;
            }
        }
        return bulls + "A" + cows + "B";
    }
}

func getHint(secret string, guess string) string {
    bulls, cows := 0, 0
    cnt := make([]int, 10)

    for i := 0; i < len(secret); i++ {
        s := secret[i]
        g := guess[i]
        if s == g {
            bulls++
        } else {
            sd := int(s - '0')
            gd := int(g - '0')
            if cnt[sd] < 0 {
                cows++
            }
            if cnt[gd] > 0 {
                cows++
            }
            cnt[sd]++
            cnt[gd]--
        }
    }

    return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B"
}

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        vector<int> cnt(10, 0);

        for (int i = 0; i < (int)secret.size(); ++i) {
            if (secret[i] == guess[i]) {
                ++bulls;
            } else {
                int s = secret[i] - '0';
                int g = guess[i] - '0';
                if (cnt[s] < 0) ++cows;
                if (cnt[g] > 0) ++cows;
                ++cnt[s];
                --cnt[g];
            }
        }

        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = cows = 0
        cnt = [0] * 10

        for s, g in zip(secret, guess):
            if s == g:
                bulls += 1
            else:
                sd = ord(s) - ord('0')
                gd = ord(g) - ord('0')
                if cnt[sd] < 0:
                    cows += 1
                if cnt[gd] > 0:
                    cows += 1
                cnt[sd] += 1
                cnt[gd] -= 1

        return f"{bulls}A{cows}B"

var getHint = function(secret, guess) {
  let bulls = 0, cows = 0;
  const cnt = new Array(10).fill(0);

  for (let i = 0; i < secret.length; i++) {
    const s = secret[i];
    const g = guess[i];
    if (s === g) {
      bulls++;
    } else {
      const sd = s.charCodeAt(0) - 48;
      const gd = g.charCodeAt(0) - 48;
      if (cnt[sd] < 0) cows++;
      if (cnt[gd] > 0) cows++;
      cnt[sd]++;
      cnt[gd]--;
    }
  }

  return `${bulls}A${cows}B`;
};

中文

题目概述

给定两个长度相同且只包含数字的字符串 secret 和 guess，返回提示字符串 xAyB：x 是公牛（数字和位置都正确），y 是奶牛（数字正确但位置错误）。

核心思路

先把同位置相等的字符计为 bulls。其余位置通过 cnt[10] 维护“secret 比 guess 多出来的各数字数量”。遇到 secret 的数字 s 时，如果 cnt[s] < 0，说明之前 guess 多了一个同数字，当前可以配成一对 cows；遇到 guess 的数字 g 时，如果 cnt[g] > 0，同理也形成一对 cows。

算法步骤

- 初始化 bulls=0、cows=0、cnt[10]=0。
- 遍历每个下标 i：
  - 若 secret[i] == guess[i]，bulls++。
  - 否则令 s、g 为对应数字。
  - 若 cnt[s] < 0，cows++，随后 cnt[s]++。
  - 若 cnt[g] > 0，cows++，随后 cnt[g]--。
- 最后返回 bulls + "A" + cows + "B"。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（仅 10 个数字桶）。

常见陷阱

- 先统计频次再算 cows 时忘了排除 bulls。
- 同一对数字被重复计数。
- 字符和数字转换处理错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0, cows = 0;
        int[] cnt = new int[10];

        for (int i = 0; i < secret.length(); i++) {
            char cs = secret.charAt(i);
            char cg = guess.charAt(i);
            if (cs == cg) {
                bulls++;
            } else {
                int s = cs - '0';
                int g = cg - '0';
                if (cnt[s] < 0) cows++;
                if (cnt[g] > 0) cows++;
                cnt[s]++;
                cnt[g]--;
            }
        }
        return bulls + "A" + cows + "B";
    }
}

func getHint(secret string, guess string) string {
    bulls, cows := 0, 0
    cnt := make([]int, 10)

    for i := 0; i < len(secret); i++ {
        s := secret[i]
        g := guess[i]
        if s == g {
            bulls++
        } else {
            sd := int(s - '0')
            gd := int(g - '0')
            if cnt[sd] < 0 {
                cows++
            }
            if cnt[gd] > 0 {
                cows++
            }
            cnt[sd]++
            cnt[gd]--
        }
    }

    return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B"
}

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        vector<int> cnt(10, 0);

        for (int i = 0; i < (int)secret.size(); ++i) {
            if (secret[i] == guess[i]) {
                ++bulls;
            } else {
                int s = secret[i] - '0';
                int g = guess[i] - '0';
                if (cnt[s] < 0) ++cows;
                if (cnt[g] > 0) ++cows;
                ++cnt[s];
                --cnt[g];
            }
        }

        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = cows = 0
        cnt = [0] * 10

        for s, g in zip(secret, guess):
            if s == g:
                bulls += 1
            else:
                sd = ord(s) - ord('0')
                gd = ord(g) - ord('0')
                if cnt[sd] < 0:
                    cows += 1
                if cnt[gd] > 0:
                    cows += 1
                cnt[sd] += 1
                cnt[gd] -= 1

        return f"{bulls}A{cows}B"

var getHint = function(secret, guess) {
  let bulls = 0, cows = 0;
  const cnt = new Array(10).fill(0);

  for (let i = 0; i < secret.length; i++) {
    const s = secret[i];
    const g = guess[i];
    if (s === g) {
      bulls++;
    } else {
      const sd = s.charCodeAt(0) - 48;
      const gd = g.charCodeAt(0) - 48;
      if (cnt[sd] < 0) cows++;
      if (cnt[gd] > 0) cows++;
      cnt[sd]++;
      cnt[gd]--;
    }
  }

  return `${bulls}A${cows}B`;
};