LeetCode 299: Bulls and Cows

Problem Restatement

We are given two equal-length digit strings:

secret
guess

We need to return a hint in this format:

"xAyB"

where:

A bull is a digit that has the same value and the same position in both strings.

A cow is a digit that exists in both strings but is in the wrong position.

Duplicate digits must be counted carefully. A digit cannot be used more than once. The official statement defines cows as non-bull digits in the guess that could be rearranged to become bulls, and notes that both strings may contain duplicate digits.

Input and Output

Function shape:

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        ...

Examples

For:

secret = "1807"
guess = "7810"

Compare by position:

There is 1 bull.

The remaining unmatched digits are:

secret: 1, 0, 7
guess:  7, 1, 0

All three can be matched as cows.

So the answer is:

"1A3B"

For:

secret = "1123"
guess = "0111"

At index 1, both strings have digit 1, so there is one bull.

Remaining unmatched digits:

secret: 1, 2, 3
guess:  0, 1, 1

Only one remaining 1 can be matched as a cow.

So the answer is:

"1A1B"

This matches the source example, which emphasizes that only one unmatched 1 is counted as a cow.

First Thought: Count Bulls and Then Count Common Digits

A simple idea is:

1. Count positions where secret[i] == guess[i].
2. Count all common digits between secret and guess.
3. Subtract bulls from the common digit count.

This can work if implemented carefully.

But it is easier to avoid double-counting by separating bull positions from non-bull positions immediately.

Key Insight

Bulls should not be counted as cows.

So while scanning the strings:

• If secret[i] == guess[i], count one bull.
• Otherwise, store the unmatched secret digit and unmatched guess digit in separate counters.

After the scan, cows are computed from the unmatched counters.

For each digit d, the number of cows using digit d is:

min(secret_count[d], guess_count[d])

because we can only match as many copies as both sides have.

Algorithm

Create:

bulls = 0
secret_count = [0] * 10
guess_count = [0] * 10

Scan every index.

If the digits match, increment bulls.

Otherwise:

secret_count[int(secret[i])] += 1
guess_count[int(guess[i])] += 1

Then compute cows:

cows = 0

for digit in range(10):
    cows += min(secret_count[digit], guess_count[digit])

Return:

f"{bulls}A{cows}B"

Correctness

Every position belongs to exactly one of two groups.

If secret[i] == guess[i], that position is a bull. The algorithm counts it as a bull and does not add it to either counter.

If secret[i] != guess[i], that position cannot be a bull. The algorithm records both digits as unmatched candidates.

After the scan, the counters contain exactly the non-bull digits from secret and guess.

For each digit, a cow requires one unmatched copy from secret and one unmatched copy from guess. If the secret side has a copies and the guess side has b copies, exactly min(a, b) cows can be formed with that digit.

Summing this value over all digits counts every possible cow once and never reuses a digit.

Therefore the algorithm returns the correct number of bulls and cows.

Complexity

Let n = len(secret).

Implementation

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

        for s_digit, g_digit in zip(secret, guess):
            if s_digit == g_digit:
                bulls += 1
            else:
                secret_count[ord(s_digit) - ord("0")] += 1
                guess_count[ord(g_digit) - ord("0")] += 1

        cows = 0

        for digit in range(10):
            cows += min(secret_count[digit], guess_count[digit])

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

Code Explanation

We count bulls directly:

bulls = 0

The two arrays count unmatched digits only:

secret_count = [0] * 10
guess_count = [0] * 10

For every aligned pair:

for s_digit, g_digit in zip(secret, guess):

we check whether it is a bull:

if s_digit == g_digit:
    bulls += 1

If it is not a bull, both digits are stored for cow counting:

secret_count[ord(s_digit) - ord("0")] += 1
guess_count[ord(g_digit) - ord("0")] += 1

Then cows are the overlap between unmatched counts:

for digit in range(10):
    cows += min(secret_count[digit], guess_count[digit])

Finally, we return the required format:

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

Testing

def test_get_hint():
    s = Solution()

    assert s.getHint("1807", "7810") == "1A3B"
    assert s.getHint("1123", "0111") == "1A1B"
    assert s.getHint("1", "0") == "0A0B"
    assert s.getHint("1", "1") == "1A0B"
    assert s.getHint("1122", "2211") == "0A4B"
    assert s.getHint("1122", "1222") == "3A0B"

    print("all tests passed")

test_get_hint()

Test meaning: