# LeetCode 299: Bulls and Cows

## Problem Restatement

We are given two equal-length digit strings:

```python
secret
guess
```

We need to return a hint in this format:

```python
"xAyB"
```

where:

| Symbol | Meaning |
|---|---|
| `x` | Number of bulls |
| `y` | Number of cows |

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

| Item | Meaning |
|---|---|
| Input | Strings `secret` and `guess` |
| Output | Hint string in format `"xAyB"` |
| Length | `secret.length == guess.length` |
| Characters | Digits only |
| Constraint | `1 <= length <= 1000` |

Function shape:

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

## Examples

For:

```python
secret = "1807"
guess = "7810"
```

Compare by position:

| Index | Secret | Guess | Result |
|---:|---|---|---|
| `0` | `1` | `7` | not bull |
| `1` | `8` | `8` | bull |
| `2` | `0` | `1` | not bull |
| `3` | `7` | `0` | not bull |

There is `1` bull.

The remaining unmatched digits are:

```python
secret: 1, 0, 7
guess:  7, 1, 0
```

All three can be matched as cows.

So the answer is:

```python
"1A3B"
```

For:

```python
secret = "1123"
guess = "0111"
```

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

Remaining unmatched digits:

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

Only one remaining `1` can be matched as a cow.

So the answer is:

```python
"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:

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

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

## Algorithm

Create:

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

Scan every index.

If the digits match, increment `bulls`.

Otherwise:

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

Then compute cows:

```python
cows = 0

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

Return:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the strings once, then scan 10 digits |
| Space | `O(1)` | The counters always have size 10 |

## Implementation

```python
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:

```python
bulls = 0
```

The two arrays count unmatched digits only:

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

For every aligned pair:

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

we check whether it is a bull:

```python
if s_digit == g_digit:
    bulls += 1
```

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

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

Then cows are the overlap between unmatched counts:

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

Finally, we return the required format:

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `"1807"`, `"7810"` | Standard example with one bull and three cows |
| `"1123"`, `"0111"` | Duplicate digits with limited cow count |
| `"1"`, `"0"` | No match |
| `"1"`, `"1"` | Single bull |
| `"1122"`, `"2211"` | All digits are cows |
| `"1122"`, `"1222"` | Bulls should not be counted as cows |