LeetCode 299 - Bulls and Cows

LeetCode Problem 299

Difficulty: 🟡 Medium
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem gives two strings, secret and guess, representing two numbers of equal length. We need to compare them and return a hint in the format "xAyB".

A "bull" is a digit that matches in both value and position. For example, if secret[i] == guess[i], then that digit contributes one bull.

A "cow" is a digit that exists in both strings but appears in different positions. Importantly, cows are counted only among digits that were not already counted as bulls. This detail becomes especially important when duplicate digits exist.

For example:

• secret = "1807"
• guess = "7810"

The digit 8 appears in the same position in both strings, so it is a bull. The digits 7, 1, and 0 exist in both strings but are misplaced, so they are cows.

The input constraints are relatively small, up to 1000 characters, but the problem still expects an efficient linear-time solution. Since the strings contain only digits, we can take advantage of fixed-size counting structures instead of more expensive general-purpose data structures.

The most important challenge is handling duplicate digits correctly. A naive implementation may accidentally count the same digit multiple times as cows. Consider:

• secret = "1123"
• guess = "0111"

There is only one bull, and only one additional 1 can count as a cow. The remaining unmatched 1 in guess should not be counted because there is no remaining unmatched 1 in secret.

Another important edge case occurs when all digits are bulls, meaning cows should be zero. Similarly, if no digits match at all, both counts should be zero.

The problem guarantees:

• Both strings have the same length
• Length is at least 1
• Inputs contain only numeric digits

These guarantees simplify the implementation because we never need to validate input format or handle mismatched lengths.

Approaches

Brute Force Approach

A straightforward approach is to first identify bulls by comparing corresponding positions in both strings. After that, for every unmatched digit in guess, we could search through the unmatched digits in secret to see whether the digit exists somewhere else.

To avoid double-counting cows, we would need an auxiliary structure to track which digits in secret have already been used.

This approach works correctly because every unmatched digit in guess is explicitly checked against the remaining unmatched digits in secret. However, the repeated searching makes it inefficient.

In the worst case, for each character we may scan almost the entire remaining string, leading to quadratic time complexity.

Optimal Approach

The key observation is that we do not actually care about the positions of unmatched digits after bulls are identified. We only care about how many times each digit appears among the unmatched characters.

This naturally suggests a counting approach.

We first count bulls directly. For non-bull positions, we track digit frequencies using an array or hash map. Since digits range only from 0 to 9, a fixed-size array of length 10 is sufficient.

One elegant optimization is to process cows in a single pass using a balance-count technique:

• If a digit from secret was previously needed by guess, we found a cow.
• If a digit from guess was previously supplied by secret, we found a cow.

This allows us to compute both bulls and cows in one traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Searches unmatched digits repeatedly
Optimal	O(n)	O(1)	Uses digit frequency counting

Algorithm Walkthrough

1. Initialize two counters, bulls and cows, both starting at 0.
2. Create a frequency array of size 10 initialized to zero. Each index represents a digit from 0 to 9.
3. Traverse both strings simultaneously using a single loop.
4. At each position:

• If secret[i] == guess[i], then this digit is a bull. Increment bulls.
• Otherwise, the digits are unmatched and may contribute to cows.

5. For unmatched digits:

• Convert both characters into integers:

• s = int(secret[i])

• g = int(guess[i])

6. Check whether the current secret digit satisfies a previously unmatched guess digit:

• If count[s] < 0, it means this digit appeared more times in unmatched guesses so far.
• Therefore, we found a matching misplaced digit, so increment cows.

7. Check whether the current guess digit satisfies a previously unmatched secret digit:

• If count[g] > 0, it means this digit appeared more times in unmatched secret digits so far.
• Therefore, increment cows.

8. Update the frequency balance:

• Increment count[s]
• Decrement count[g]

9. After processing all characters, return the result formatted as:

"{bulls}A{cows}B"

Why it works

The frequency array maintains the difference between unmatched digits seen in secret and unmatched digits seen in guess.

• A positive value means extra occurrences from secret
• A negative value means extra occurrences from guess

Whenever processing a new unmatched digit resolves a previously unmatched occurrence from the opposite string, we have discovered a valid cow.

Because every unmatched digit is balanced exactly once, duplicate digits are handled correctly without overcounting.

Python Solution

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = 0
        cows = 0
        
        count = [0] * 10
        
        for s_char, g_char in zip(secret, guess):
            if s_char == g_char:
                bulls += 1
            else:
                s = int(s_char)
                g = int(g_char)
                
                if count[s] < 0:
                    cows += 1
                
                if count[g] > 0:
                    cows += 1
                
                count[s] += 1
                count[g] -= 1
        
        return f"{bulls}A{cows}B"

The implementation closely follows the algorithm described earlier.

The variables bulls and cows store the final counts. The count array tracks frequency imbalances between unmatched digits from secret and guess.

The loop processes both strings simultaneously using zip. When characters match exactly, the digit is immediately classified as a bull.

For mismatched digits, the code checks whether the current digit can resolve a previously unmatched occurrence from the opposite string. This is the critical insight that allows cows to be counted in one pass.

The frequency updates happen after the checks because we want to compare against previously seen unmatched digits, not the current one.

Finally, the formatted string is returned in the required "xAyB" format.

Go Solution

package main

import "fmt"

func getHint(secret string, guess string) string {
    bulls := 0
    cows := 0

    count := make([]int, 10)

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

            if count[s] < 0 {
                cows++
            }

            if count[g] > 0 {
                cows++
            }

            count[s]++
            count[g]--
        }
    }

    return fmt.Sprintf("%dA%dB", bulls, cows)
}

The Go implementation is nearly identical to the Python version, but there are a few language-specific differences.

Go strings are indexed as bytes, so digit conversion is performed using:

int(secret[i] - '0')

instead of Python's int() conversion.

The frequency array is created using make([]int, 10), which initializes all entries to zero automatically.

String formatting uses fmt.Sprintf rather than Python f-strings.

Since the constraints are small and digit values are tiny, integer overflow is not a concern.

Worked Examples

Example 1

secret = "1807"
guess  = "7810"

Index	secret[i]	guess[i]	Bulls	Cows	Count State
0	1	7	0	0	+1 for 1, -1 for 7
1	8	8	1	0	unchanged
2	0	1	1	1	digit 1 resolves previous unmatched secret digit
3	7	0	1	3	digit 7 and 0 each resolve previous imbalance

Final result:

1A3B

Example 2

secret = "1123"
guess  = "0111"

Index	secret[i]	guess[i]	Bulls	Cows	Count State
0	1	0	0	0	+1 for 1, -1 for 0
1	1	1	1	0	unchanged
2	2	1	1	1	guess digit 1 resolves earlier unmatched secret 1
3	3	1	1	1	no additional match

Final result:

1A1B

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Frequency array size is fixed at 10

The algorithm performs a single pass through both strings, so runtime grows linearly with input length.

The extra memory usage is constant because the counting array always contains exactly 10 entries regardless of input size.

Test Cases

solution = Solution()

assert solution.getHint("1807", "7810") == "1A3B"  # basic mixed bulls and cows
assert solution.getHint("1123", "0111") == "1A1B"  # duplicate digits
assert solution.getHint("1234", "1234") == "4A0B"  # all bulls
assert solution.getHint("1234", "5678") == "0A0B"  # no matches
assert solution.getHint("1122", "2211") == "0A4B"  # all cows
assert solution.getHint("1", "1") == "1A0B"        # minimum size, exact match
assert solution.getHint("1", "0") == "0A0B"        # minimum size, no match
assert solution.getHint("1111", "1111") == "4A0B"  # repeated identical digits
assert solution.getHint("1112", "2211") == "0A2B"  # repeated digits with partial cows
assert solution.getHint("9876543210", "0123456789") == "0A10B"  # all digits misplaced

Test	Why
"1807", "7810"	Standard example with both bulls and cows
"1123", "0111"	Verifies duplicate handling
"1234", "1234"	All digits match exactly
"1234", "5678"	No shared digits
"1122", "2211"	All digits are cows
"1", "1"	Smallest valid matching input
"1", "0"	Smallest valid non-matching input
"1111", "1111"	Repeated identical digits
"1112", "2211"	Partial duplicate overlap
"9876543210", "0123456789"	Large cow-only scenario

Edge Cases

One important edge case involves duplicate digits appearing more times in guess than in secret. For example:

secret = "1123"
guess  = "1111"

A naive implementation might incorrectly count too many cows because it sees multiple matching digits. The frequency-balance method prevents this by only counting cows when an unmatched occurrence truly exists on the opposite side.

Another important case occurs when every digit is already a bull. For example:

secret = "1234"
guess  = "1234"

In this situation, cows must remain zero because cows are defined only among non-bull digits. The implementation handles this naturally because matching positions bypass the frequency logic entirely.

A third subtle case is when all matches are cows and none are bulls:

secret = "1122"
guess  = "2211"

Every digit exists in both strings but appears in the wrong position. Some implementations accidentally undercount or overcount due to duplicate handling. The balance-array approach correctly matches each unmatched digit exactly once, producing 0A4B.

A final edge case involves the smallest possible input length:

secret = "1"
guess  = "0"

The algorithm still works correctly because the loop structure and counting logic do not depend on string length greater than one.