Problem

You are playing the Bulls and Cows 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.

Examples

Example 1:

1
2
3
4
5
6
7

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

Example 2:

1
2
3
4
5
6
7
8

Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1 1 2 3"        "1 1 2 3"
   |       or       |
"0 1 1 1"        "0 1 1 1"
     ⎻                  ⎻
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.

Solution

Method 1 – Using Hash Maps

Intuition

We need to count how many digits are bulls (correct digit and position) and cows (correct digit, wrong position). By using a hash map to track the frequency of unmatched digits in the secret, we can efficiently count cows when the same digit appears in the guess but not as a bull.

Approach

  1. Initialize counters for bulls and cows.
  2. Use a hash map to count the frequency of unmatched digits in the secret.
  3. First pass: For each position, if the digit matches, increment bulls; otherwise, add the secret digit to the hash map.
  4. Second pass: For each position, if not a bull and the guess digit exists in the hash map, increment cows and decrement the hash map count.
  5. Return the result in the format “xAyB”.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        unordered_map<char, int> freq;
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) {
                bulls++;
            } else {
                freq[secret[i]]++;
            }
        }
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] != guess[i] && freq[guess[i]] > 0) {
                cows++;
                freq[guess[i]]--;
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0, cows = 0;
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i), g = guess.charAt(i);
            if (s == g) {
                bulls++;
            } else {
                freq.put(s, freq.getOrDefault(s, 0) + 1);
            }
        }
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i), g = guess.charAt(i);
            if (s != g && freq.getOrDefault(g, 0) > 0) {
                cows++;
                freq.put(g, freq.get(g) - 1);
            }
        }
        return bulls + "A" + cows + "B";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = cows = 0
        freq = {}
        for i in range(len(secret)):
            if secret[i] == guess[i]:
                bulls += 1
            else:
                freq[secret[i]] = freq.get(secret[i], 0) + 1
        for i in range(len(secret)):
            if secret[i] != guess[i] and freq.get(guess[i], 0) > 0:
                cows += 1
                freq[guess[i]] -= 1
        return f"{bulls}A{cows}B"

Complexity

  • ⏰ Time complexity: O(n), where n is the length of secret, since we process each digit twice (once for bulls, once for cows).
  • 🧺 Space complexity: O(1), since the hash map stores at most 10 digits.

Method 2 – Using Array as Hash Map

Intuition

Since the digits are from 0 to 9, we can use two arrays to count the frequency of unmatched digits in secret and guess. This allows us to efficiently count cows by comparing the minimum frequency of each digit in both arrays after counting bulls.

Approach

  1. Initialize counters for bulls and cows, and two arrays of size 10 for digit frequencies in secret and guess.
  2. First pass: For each position, if the digit matches, increment bulls; otherwise, increment the frequency in the respective array.
  3. After the first pass, for each digit from 0 to 9, add the minimum frequency from both arrays to cows.
  4. Return the result in the format “xAyB”.

Complexity

  • ⏰ Time complexity: O(n), where n is the length of secret, since we process each digit twice (once for bulls, once for cows).
  • 🧺 Space complexity: O(1), since the arrays have fixed size (10 digits).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        int arr1[10] = {}, arr2[10] = {};
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) {
                bulls++;
            } else {
                arr1[secret[i] - '0']++;
                arr2[guess[i] - '0']++;
            }
        }
        for (int i = 0; i < 10; ++i) {
            cows += min(arr1[i], arr2[i]);
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0, cows = 0;
        int[] arr1 = new int[10];
        int[] arr2 = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i), g = guess.charAt(i);
            if (s == g) {
                bulls++;
            } else {
                arr1[s - '0']++;
                arr2[g - '0']++;
            }
        }
        for (int i = 0; i < 10; i++) {
            cows += Math.min(arr1[i], arr2[i]);
        }
        return bulls + "A" + cows + "B";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = cows = 0
        arr1 = [0] * 10
        arr2 = [0] * 10
        for i in range(len(secret)):
            if secret[i] == guess[i]:
                bulls += 1
            else:
                arr1[int(secret[i])] += 1
                arr2[int(guess[i])] += 1
        for i in range(10):
            cows += min(arr1[i], arr2[i])
        return f"{bulls}A{cows}B"