Solution: Bulls and Cows

Statement

You are playing a number guessing game called “Bulls and Cows” with a friend.

You write down a secret number, and your friend tries to guess it. After each guess, you provide a hint based on the following:

• Bulls: The number of digits that are in the correct position in the guess.

• Cows: The number of digits that are in both the secret and the guess but in different positions. (These are non-bull digits that could become bulls if rearranged.)

Your task is to return a hint for the guess, formatted as “xAyB”, where:

• x is the number of bulls.

• y is the number of cows.

Note: Both the secret number and the guess may contain duplicate digits.

Constraints:

• $1 <=$ secret.length, guess.length $<= 10^3$

• secret.length == guess.length

• secret and guess consist of digits only.

Solution

The solution uses a hash table with a single pass approach to determine the number of bulls and cows in the given strings secret and guess. Bulls are defined as the digits in the correct position, while cows are the digits present in both strings but in different positions. The core idea is to maintain a count of unmatched digits using a hash table and compute bulls and cows simultaneously.

Now, let’s walk through the steps of the solution:

1. We initialize a hash table dict to keep track of the counts of unmatched digits.

2. We also initialize two variables, bulls and cows, to count the bulls and cows, respectively.

3. Next, we iterate through each character of the secret and in each iteration, we retrieve the corresponding character at the same index from the guess. For each pair of characters s from secret and g from guess, we perform the following checks:

   1. If the characters s and g are the same, we increment the bulls counter by $1$, as this means there is a digit in the correct position.

   2. Otherwise, if the characters are not the same, we check how many cows can be formed:

      1. We add to the cows counter based on the count of unmatched digits stored in dict. Specifically, we add $1$ if the count of s in dict is less than $0$ (indicating that s was guessed before) and add $1$ if the count of g in dict is greater than $0$ (indicating that g was part of the secret previously).

      2. We then update the counts in dict by incrementing the count for s and decrementing the count for g to reflect the unmatched digits.

4. Finally, we return the result formatted as "{bulls}A{cows}B", where bulls is the count of bulls and cows is the count of cows.

Let’s look at the following illustration to get a better understanding: