Problem statement

In the Bulls and Cows game one player picks a secret digit string and the other makes a guess of the same length. The hint for a guess has two numbers:

• bulls — positions where the guess has the same digit as the secret;
• cows — digits of the guess that occur in the secret but at a different position, where every secret digit can be matched at most once and bull positions are not available for cows.

Put differently, after removing the bull positions from both strings, the cows are the size of the largest one-to-one matching of equal digits between what is left.

Return the hint as "xAyB", where x is the number of bulls and y the number of cows. Both strings may contain repeated digits.

Example 1

Input: secret = "9305", guess = "9530"
Output: "1A3B"
Explanation: The 9 is a bull; 5, 3 and 0 are all in the secret elsewhere.

Example 2

Input: secret = "2024", guess = "4202"
Output: "0A4B"

Example 3

Input: secret = "1112", guess = "1221"
Output: "1A2B"
Explanation: Index 0 is a bull. Left over: secret `112`, guess `221` — one `1` and one `2` match, the second `2` has no partner.

Constraints

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret and guess consist of digits only

Hints for Bulls and Cows

1. Hint 1

   Bulls are easy: compare position by position.

2. Hint 2

   For the cows, only the non-bull positions matter, and their order does not matter — just how many of each digit each side has left.

3. Hint 3

   Count digits on each side over the non-bull positions; the cows are the sum over digits of the smaller of the two counts.

How to solve Bulls and Cows

Bulls are positional; cows are a multiset intersection of the leftover digits, which is the sum of per-digit minimum counts.

Approach

1. Keep two arrays of 10 counters, one for the secret and one for the guess.
2. Scan the positions: if secret[i] == guess[i], count a bull; otherwise increment the counter of secret[i] on the secret side and guess[i] on the guess side.
3. The cows are Σ_d min(secretCount[d], guessCount[d]).
4. Return bulls + "A" + cows + "B".

Why it works

A digit d left over a times in the secret and b times in the guess can be paired at most min(a, b) times, since each secret digit is used once, and that many pairs can always be formed; different digits never interact, so summing the minimums gives the largest matching.

Complexity

• Time — O(n)
• Space — O(1) — two arrays of 10 counters

Pitfalls

• Counting cows before removing the bull positions double-counts digits that are bulls.
• With repeated digits, a single guess digit cannot match two secret digits — use the minimum, not the guess count.
• The answer is a string such as "0A0B", not two numbers.

Reference solution

Python

def getHint(secret: str, guess: str) -> str:
    bulls = 0
    cs = [0] * 10
    cg = [0] * 10
    for a, b in zip(secret, guess):
        if a == b:
            bulls += 1
        else:
            cs[ord(a) - 48] += 1
            cg[ord(b) - 48] += 1
    cows = sum(min(cs[d], cg[d]) for d in range(10))
    return str(bulls) + "A" + str(cows) + "B"

Java

public static String getHint(String secret, String guess) {
    int bulls = 0, cows = 0;
    int[] cs = new int[10], cg = new int[10];
    for (int i = 0; i < secret.length(); i++) {
        char a = secret.charAt(i), b = guess.charAt(i);
        if (a == b) bulls++;
        else {
            cs[a - '0']++;
            cg[b - '0']++;
        }
    }
    for (int d = 0; d < 10; d++) cows += Math.min(cs[d], cg[d]);
    return bulls + "A" + cows + "B";
}

C++

string getHint(string secret, string guess) {
    int bulls = 0, cows = 0;
    int cs[10] = {0}, cg[10] = {0};
    for (size_t i = 0; i < secret.size(); i++) {
        if (secret[i] == guess[i]) bulls++;
        else {
            cs[secret[i] - '0']++;
            cg[guess[i] - '0']++;
        }
    }
    for (int d = 0; d < 10; d++) cows += min(cs[d], cg[d]);
    return to_string(bulls) + "A" + to_string(cows) + "B";
}

JavaScript

var getHint = function(secret, guess) {
    var bulls = 0, cows = 0;
    var cs = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    var cg = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for (var i = 0; i < secret.length; i++) {
        if (secret[i] === guess[i]) bulls++;
        else {
            cs[secret.charCodeAt(i) - 48]++;
            cg[guess.charCodeAt(i) - 48]++;
        }
    }
    for (var d = 0; d < 10; d++) cows += Math.min(cs[d], cg[d]);
    return bulls + "A" + cows + "B";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium