# Bulls and Cows
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/bulls-and-cows)
Canonical: https://scaleengineer.com/dsa/problems/bulls-and-cows
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Epic Systems](https://scaleengineer.com/companies/epic-systems), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [CARS24](https://scaleengineer.com/companies/cars24)
---
## Problem
You are playing the **[Bulls and Cows](https://en.wikipedia.org/wiki/Bulls%5Fand%5FCows)** game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

* The number of "bulls", which are digits in the guess that are in the correct position.
* The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number `secret` and your friend's guess `guess`, return _the hint for your friend's guess_.

The hint should be formatted as `"xAyB"`, where `x` is the number of bulls and `y` is the number of cows. Note that both `secret` and `guess` may contain duplicate digits.

**Example 1:**

**Input:** secret = "1807", guess = "7810"
**Output:** "1A3B"
**Explanation:** Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

**Example 2:**

**Input:** secret = "1123", guess = "0111"
**Output:** "1A1B"
**Explanation:** Bulls are connected with a '|' and cows are underlined:
"1123"        "1123"
  |      or     |
"0111"        "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.

**Constraints:**

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

# Approaches
## Brute-Force with Marking (Two Passes)
This approach uses two passes over the input strings. The first pass identifies and counts "bulls" (digits in the correct position). The second pass uses nested loops to find "cows" (correct digits in the wrong position) among the remaining characters. To avoid recounting, boolean flags are used to mark characters that have been matched as either a bull or a cow.
**Time:** O(n^2), where `n` is the length of the strings. The first pass is `O(n)`, but the second pass involves nested loops, leading to `O(n^2)` in the worst case. · **Space:** O(n), where `n` is the length of the strings. This is required to store the `secretUsed` and `guessUsed` boolean arrays.
**Pros:** Simple to understand and implement.; The logic directly follows the problem definition.
**Cons:** Inefficient due to the `O(n^2)` time complexity, which can be slow for larger inputs.; Uses extra space proportional to the input size.
### Explanation
This method directly simulates the matching process. It first iterates through the strings to find all exact matches (bulls) and marks them as used. Then, it performs a second, nested iteration on the remaining, unused characters to find matches in wrong positions (cows). This ensures that a character is not counted as both a bull and a cow, and also that each character is used in at most one match.

```java
class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        int n = secret.length();
        boolean[] secretUsed = new boolean[n];
        boolean[] guessUsed = new boolean[n];

        // First pass for bulls
        for (int i = 0; i < n; i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                bulls++;
                secretUsed[i] = true;
                guessUsed[i] = true;
            }
        }

        // Second pass for cows
        for (int i = 0; i < n; i++) {
            if (guessUsed[i]) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (!secretUsed[j] && secret.charAt(j) == guess.charAt(i)) {
                    cows++;
                    secretUsed[j] = true;
                    break; // Found a match for guess[i], move to the next guess character
                }
            }
        }

        return bulls + "A" + cows + "B";
    }
}
```
### Algorithm
- Initialize `bulls` and `cows` to 0.
- Get the length `n` of the strings.
- Create two boolean arrays, `secretUsed` and `guessUsed`, of size `n`, initialized to `false`.
- **First Pass (Bulls):** Iterate from `i = 0` to `n-1`. If `secret.charAt(i)` equals `guess.charAt(i)`, increment `bulls` and set `secretUsed[i]` and `guessUsed[i]` to `true`.
- **Second Pass (Cows):** Iterate through the `guess` string with index `i`. If `guessUsed[i]` is `false`, start an inner loop through the `secret` string with index `j`.
- In the inner loop, if `secretUsed[j]` is `false` and `guess.charAt(i)` equals `secret.charAt(j)`, we've found a cow. Increment `cows`, set `secretUsed[j]` to `true`, and break the inner loop to prevent matching the same `secret` character again.
- Finally, format the result as a string: `bulls + "A" + cows + "B"`.

## Two-Pass with Frequency Count
This approach improves upon the brute-force method by using frequency maps (or arrays) to count characters, avoiding the nested loop for finding cows. It still uses two passes: the first pass identifies bulls and simultaneously builds frequency counts for the non-bull characters. The second pass calculates the number of cows by comparing the frequency counts.
**Time:** O(n), where `n` is the length of the strings. The first pass takes `O(n)` and the second pass takes `O(1)` (since it iterates 10 times). · **Space:** O(1), as the frequency arrays have a constant size (10), independent of the input string length.
**Pros:** Much more efficient than the brute-force approach with linear time complexity.; Uses constant extra space, as the size of the frequency arrays does not depend on the input size.
**Cons:** Requires two separate passes over the data, which is slightly less efficient than a single-pass solution.
### Explanation
The key idea is to separate the bull-finding logic from the cow-finding logic. After the first pass identifies all bulls, we are left with two sets of characters (from `secret` and `guess`) that are at incorrect positions. The number of cows is simply the number of characters common to both these sets. We can find this by counting the frequencies of each digit in both sets and then for each digit, taking the minimum of the two counts. This avoids the expensive `O(n^2)` search for cows.

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

        // First pass for bulls and counting non-bull characters
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s == g) {
                bulls++;
            } else {
                secretCounts[s - '0']++;
                guessCounts[g - '0']++;
            }
        }

        // Second pass for cows
        for (int i = 0; i < 10; i++) {
            cows += Math.min(secretCounts[i], guessCounts[i]);
        }

        return bulls + "A" + cows + "B";
    }
}
```
### Algorithm
- Initialize `bulls` and `cows` to 0.
- Create two integer arrays, `secretCounts` and `guessCounts`, of size 10 (for digits 0-9), initialized to 0.
- **First Pass (Bulls and Frequencies):** Iterate from `i = 0` to `n-1`.
- If `secret.charAt(i)` equals `guess.charAt(i)`, increment `bulls`.
- Otherwise, increment the count for `secret.charAt(i)` in `secretCounts` and for `guess.charAt(i)` in `guessCounts`.
- **Second Pass (Cows):** Iterate from `d = 0` to 9. For each digit, the number of cows is the minimum of its count in `secretCounts` and `guessCounts`. Add this minimum value to the total `cows`.
- Finally, format the result as a string: `bulls + "A" + cows + "B"`.

## One-Pass with Single Frequency Array
This is the most optimal approach, solving the problem in a single pass. It calculates bulls and cows simultaneously. A single frequency array is used to keep track of the balance of non-bull digits between the `secret` and `guess` strings. A positive count for a digit indicates a surplus in `secret`, while a negative count indicates a surplus in `guess`.
**Time:** O(n), where `n` is the length of the strings, as we iterate through the strings only once. · **Space:** O(1), as the frequency array has a constant size (10).
**Pros:** Most efficient solution with `O(n)` time and `O(1)` space.; Processes the input in a single pass, which can be faster in practice due to better cache performance.; It's a clever and compact way to solve the problem.
**Cons:** The logic for updating cows and the frequency array can be slightly less intuitive to grasp at first compared to the two-pass approach.
### Explanation
This elegant solution processes both strings in a single loop. For each position, it first checks for a bull. If it's not a bull, it uses a single array to track the counts of mismatched digits. A positive value `counts[d]` means `secret` has seen `d` more times than `guess` among mismatched characters, while a negative value means the opposite. A cow is found whenever we process a digit that can cancel out a previously recorded surplus from the other string. For example, if we process `guess.charAt(i) = d` and `counts[d]` is positive, it means there's an unmatched `d` from `secret` available, forming a cow. Similarly, if we process `secret.charAt(i) = d` and `counts[d]` is negative, there's an unmatched `d` from `guess` available.

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

        for (int i = 0; i < secret.length(); i++) {
            int s = secret.charAt(i) - '0';
            int g = guess.charAt(i) - '0';

            if (s == g) {
                bulls++;
            } else {
                // If guess digit g was seen in secret before (secret has a surplus)
                if (counts[g] > 0) {
                    cows++;
                }
                // If secret digit s was seen in guess before (guess has a surplus)
                if (counts[s] < 0) {
                    cows++;
                }
                // Update balances
                counts[s]++;
                counts[g]--;
            }
        }
        return bulls + "A" + cows + "B";
    }
}
```
### Algorithm
- Initialize `bulls` and `cows` to 0.
- Create a single integer array `counts` of size 10, initialized to 0.
- **Single Pass:** Iterate from `i = 0` to `n-1`.
- Let `s` be the digit from `secret` and `g` be the digit from `guess` at index `i`.
- If `s == g`, increment `bulls`.
- If `s != g`:
  - Check `counts[g]`. If it's positive, it means we've previously seen this digit in `secret` (as a non-bull) that can now be matched with the current `g`. So, we've found a cow. Increment `cows`.
  - Check `counts[s]`. If it's negative, it means we've previously seen this digit in `guess` (as a non-bull) that can now be matched with the current `s`. So, we've found a cow. Increment `cows`.
  - Update the balance: increment `counts[s]` (we've seen one more `s`) and decrement `counts[g]` (we've seen one more `g`).
- Finally, format the result as a string: `bulls + "A" + cows + "B"`.

# Solutions
### Java

```java
class Solution { public String getHint ( String secret , String guess ) { int x = 0 , y = 0 ; int [] cnt1 = new int [ 10 ]; int [] cnt2 = new int [ 10 ]; for ( int i = 0 ; i < secret . length (); ++ i ) { int a = secret . charAt ( i ) - '0' , b = guess . charAt ( i ) - '0' ; if ( a == b ) { ++ x ; } else { ++ cnt1 [ a ]; ++ cnt2 [ b ]; } } for ( int i = 0 ; i < 10 ; ++ i ) { y += Math . min ( cnt1 [ i ], cnt2 [ i ]); } return String . format ( "%dA%dB" , x , y ); } }
```

### CPP

```cpp
class Solution { public: string getHint ( string secret , string guess ) { int x = 0 , y = 0 ; vector < int > cnt1 ( 10 ); vector < int > cnt2 ( 10 ); for ( int i = 0 ; i < secret . size (); ++ i ) { int a = secret [ i ] - '0' , b = guess [ i ] - '0' ; if ( a == b ) ++ x ; else { ++ cnt1 [ a ]; ++ cnt2 [ b ]; } } for ( int i = 0 ; i < 10 ; ++ i ) y += min ( cnt1 [ i ], cnt2 [ i ]); return to_string ( x ) + "A" + to_string ( y ) + "B" ; } };
```

### Python

```python
class Solution : def getHint ( self , secret : str , guess : str ) -> str : x = y = 0 cnt1 = [ 0 ] * 10 cnt2 = [ 0 ] * 10 for i in range ( len ( secret )): if secret [ i ] == guess [ i ]: x += 1 else : cnt1 [ int ( secret [ i ])] += 1 cnt2 [ int ( guess [ i ])] += 1 for i in range ( 10 ): y += min ( cnt1 [ i ], cnt2 [ i ]) return f ' { x } A { y } B'
```