How do you solve Bulls and Cows?

Iterate once through both strings simultaneously. For each index, if digits match, increment bulls. Otherwise, increment counts in secret_counts and guess_counts hash maps. After the iteration, sum the minimum counts for each digit in guess_counts against secret_counts to get cows. Return the formatted string combining bulls and cows.

What pattern does Bulls and Cows use?

The Pattern: Hash Maps (Frequency Counting with Complement Matching) The Heuristic: Separate exact matches from partial matches by first identifying and excluding exact matches, then use frequency maps to count how many unmatched digits overlap, ensuring no double counting.

Bulls and Cows | Hash Maps

Q: What is the time complexity of Bulls and Cows?

O(n). The solution iterates through the strings once to count bulls and build frequency maps, then iterates through the keys of guess_counts (at most 10 digits) to compute cows, resulting in linear time relative to input length.

Problem

Given two strings secret and guess, return a hint string that indicates how many digits in guess match the digits in secret exactly in both digit and position (bulls) and how many digits match the secret but are in the wrong position (cows).

1 ≤ secret.length, guess.length ≤ 1000
secret.length == guess.length
secret and guess consist of digits only

Example

Input: secret = "1807", guess = "7810"

Output: "1A3B"

The algorithm iterates through each position comparing digits. At index 0, secret has '1' and guess has '7' — no exact match, so counts for '1' and '7' are recorded. At index 1, secret has '8' and guess has '8' — an exact match (bull), so bulls increment to 1. At index 2, secret has '0' and guess has '1' — no exact match, counts recorded. At index 3, secret has '7' and guess has '0' — no exact match, counts recorded. After this pass, bulls = 1. The unmatched digits are tallied in two hash maps for secret and guess respectively.

Approach

Straightforward Solution

A naive approach would compare every digit in guess against every digit in secret to count cows, resulting in O(n²) time complexity, which is inefficient for longer strings.

Core Observation

Exact matches (bulls) are straightforward to count by comparing characters at the same index. However, counting cows requires tracking unmatched digits separately because they must be matched across positions without double counting.

Path to Optimal

Preview

The key insight is to separate bulls from cows by first counting exact matches and then using hash maps to count frequencies of unmatched digits in both strings. The number of cows for each digit is the minimum count of that digit in secret and guess unmatched sets…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate once through both strings simultaneously. For each index, if digits match, increment bulls…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The solution iterates through the strings once to count bulls and build frequency maps, then iterates through the keys of guess_counts (at most 10 digits) to compute cows, resulting in linear time relative to input length.

Space

O(1)

The hash maps store counts for digits 0-9 only, so space usage is constant and does not scale with input size.

Solution

Python

1class Solution:
  def getHint(self, secret: str, guess: str) -> str:
      bulls = 0
      secret_counts = {}
      guess_counts = {}
6
      for index in range(len(secret)):
          secret_digit = secret[index]
          guess_digit = guess[index]
10
          if secret_digit == guess_digit:
              bulls += 1
          else:
              secret_counts[secret_digit] = secret_counts.get(secret_digit, 0) + 1
              guess_counts[guess_digit] = guess_counts.get(guess_digit, 0) + 1
16
      cows = 0
18
      for digit in guess_counts:
          cows += min(guess_counts[digit], secret_counts.get(digit, 0))
21
      return str(bulls) + "A" + str(cows) + "B"

Step-by-Step Solution

1

Count Bulls and Build Frequency Maps for Unmatched Digits

3bulls = 0
4secret_counts = {}
5guess_counts = {}
7for index in range(len(secret)):
8    secret_digit = secret[index]
9    guess_digit = guess[index]
11    if secret_digit == guess_digit:
12        bulls += 1
14        secret_counts[secret_digit] = secret_counts.get(secret_digit, 0) + 1
15        guess_counts[guess_digit] = guess_counts.get(guess_digit, 0) + 1

Objective

To identify exact matches and simultaneously record the frequency of unmatched digits in both secret and guess.

Key Insight

By iterating once over both strings, the algorithm efficiently separates bulls from potential cows. Exact matches are counted immediately, while unmatched digits are recorded in hash maps. This separation is crucial because it prevents double counting and sets up a simple frequency comparison to find cows.

Interview Quick-Check

Core Logic

Increment bulls when digits match at the same index; otherwise, increment counts in secret_counts and guess_counts for unmatched digits.

State & Boundaries

Iterate over the entire length of the strings, ensuring all positions are checked exactly once.

Common Pitfalls & Bugs

Failing to separate bulls before counting frequencies leads to incorrect cow counts due to double counting exact matches.

2

Calculate Cows by Summing Minimum Frequency Overlaps

To compute the number of cows by summing the minimum counts of each digit present in both secret and guess unmatched frequency maps.

3

Format and Return the Final Hint String

To construct the output string in the format 'xAyB' where x is bulls and y is cows.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

if secret_digit == guess_digit:

Check if the secret and guess digits match exactly at this position.

This check is the critical decision point that separates bulls from cows, ensuring exact matches are counted immediately and excluded from frequency maps.

Line 20 Critical

cows += min(guess_counts[digit], secret_counts.get(digit, 0))

Add the minimum frequency of the digit between guess and secret unmatched counts to cows.

This line embodies the core logic for counting cows by matching frequencies of unmatched digits, preventing double counting and ensuring correctness.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why must bulls be counted separately before counting cows using frequency maps?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Bulls and Cows from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Bulls and Cows drill

or drill a free problem

1	`class Solution:`
2	`def getHint(self, secret: str, guess: str) -> str:`
3	`bulls = 0`
4	`secret_counts = {}`
5	`guess_counts = {}`
6
7	`for index in range(len(secret)):`
8	`secret_digit = secret[index]`
9	`guess_digit = guess[index]`
10
11	`if secret_digit == guess_digit:`
12	`bulls += 1`
13	`else:`
14	`secret_counts[secret_digit] = secret_counts.get(secret_digit, 0) + 1`
15	`guess_counts[guess_digit] = guess_counts.get(guess_digit, 0) + 1`
16
17	`cows = 0`
18
19	`for digit in guess_counts:`
20	`cows += min(guess_counts[digit], secret_counts.get(digit, 0))`
21
22	`return str(bulls) + "A" + str(cows) + "B"`

3	`bulls = 0`
4	`secret_counts = {}`
5	`guess_counts = {}`
7	`for index in range(len(secret)):`
8	`secret_digit = secret[index]`
9	`guess_digit = guess[index]`
11	`if secret_digit == guess_digit:`
12	`bulls += 1`
14	`secret_counts[secret_digit] = secret_counts.get(secret_digit, 0) + 1`
15	`guess_counts[guess_digit] = guess_counts.get(guess_digit, 0) + 1`