Domain 2MediumCORE

Bulls and Cows

We are given two strings of equal length containing digits: secret (the hidden number) and guess. We need to return a formatted string 'xAyB', where x is the count of 'bulls' and y is the count of 'cows'.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table

299. Bulls and Cows

Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 44.7%


Problem Breakdown

We are given two strings of equal length containing digits: secret (the hidden number) and guess. We need to return a formatted string "xAyB", where x is the count of “bulls” and y is the count of “cows”.

  • Bull (A): A digit in guess that matches the corresponding digit in secret at the same index.
  • Cow (B): A digit in guess that exists in secret but not at the correct position (wrong index). Crucially, this is a non-bull match where digits can be rearranged to become bulls.

Key Constraints & Tricky Parts:

  1. Duplicates: The problem explicitly states duplicates are allowed and must be handled correctly. A digit in secret cannot contribute to both a Bull and a Cow simultaneously if it’s the same instance, but multiple instances of the same digit can exist (e.g., two ‘1’s). We need to ensure we don’t double-count matches for digits that appear more than once.
  2. Format: The output must be strictly "xAyB".

Intuition

A brute-force approach would involve checking every position in guess against secret, but determining the number of cows is tricky because a digit might match multiple times or not at all depending on how many instances exist. Checking permutations to find valid cow positions leads to exponential complexity, which we want to avoid.

The core insight relies on frequency counting (Hash Table/Array).

  1. Bulls are easy: Iterate through indices and count exact matches (secret[i] == guess[i]). These specific digits should be “consumed” so they don’t contribute to the cow count later.
  2. Cows: For any digit d, if it appears in both strings, we can match at most as many times as the minimum frequency of that digit exists between them (excluding bulls).
  3. However, a simpler mathematical relationship works: The total number of matching digits possible regardless of position is determined by summing min(count_secret[d], count_guess[d]) for all digits d. Since Bulls are exact matches included in this calculation, we can simply subtract the actual Bull count from this Total Potential Matches to get Cows.
    • Wait, let’s refine that logic: If I calculate total potential matches based on frequency (ignoring position), every bull is inherently a match counted there. Every cow is also a match counted there but not at the correct index. So Cows = sum(min(frequencies)) - Bulls. This avoids complex state management during iteration and simplifies to two passes: one for counting frequencies, one for finding bulls (or vice versa).

Approach

  1. Initialize Counters: Create frequency arrays of size 10 (for digits ‘0’-‘9’) for both secret and guess. This is O(1) space since the alphabet is fixed.
  2. Count Frequencies: Iterate through both strings once to populate these counters.
  3. Identify Bulls & Adjust Counts: Iterate through indices again (or just iterate one string). If characters match, increment a bulls counter and decrement the frequency count for that digit in both maps?
    • Actually, using the formula derived in Intuition (Cows = sum(min) - bulls) is cleaner. However, to be precise about “consumed” digits:
    • Better Implementation Strategy: Iterate through indices ii. If secret[i] == guess[i], increment bulls. Else if we can match the digit (checking remaining counts), it’s a cow? No, that requires complex logic.
    • Optimal Algorithm:
      1. Count frequencies of all digits in both strings into two arrays/maps (countS and countG).
      2. Iterate through indices ii. If secret[i] == guess[i], increment bulls. Decrement the count for that digit in both maps immediately? No, if we decrement on mismatch too it gets messy.
      3. Correct Logic: Count frequencies first (ignoring position). Then iterate to find Bulls and subtract them from total potential matches calculated by frequency sums. Wait, simply: cows = sum(min(countS[d], countG[d])) - bulls. This works perfectly because every Bull is a valid match in the frequency domain that we must exclude from Cows.
    1. Construct Output: Format string as "xAyB".

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of secret (or guess). We iterate through both strings once to build frequency maps and potentially a second time or constant 10 iterations for summing. Since digits are fixed ‘0’-‘9’, map operations are O(1).
  • Space Complexity: O(1)O(1). The space used is proportional to the number of unique characters (digits), which is bounded by 10, regardless of input size.

Solution

from typing import List

def getHint(secret: str, guess: str) -> str:
    # Frequency arrays for digits '0'-'9'. 
    # Using lists instead of dicts for slightly better performance given fixed domain.
    countS = [0] * 10
    countG = [0] * 10
    
    n = len(secret)
    
    # Pass 1: Count frequencies in both strings
    for i in range(n):
        digit_s = int(secret[i])
        digit_g = int(guess[i])
        
        countS[digit_s] += 1
        countG[digit_g] += 1
        
    bulls = 0
    
    # Pass 2: Count Bulls and calculate Cows based on frequency logic
    for i in range(n):
        if secret[i] == guess[i]:
            bulls += 1
            
    # Calculate total potential matches (Bulls + Cows) using min frequencies
    cows = 0
    for d in range(10):
        common_matches = min(countS[d], countG[d])
        cows += common_matches
        
    # Subtract Bulls from Total Matches to get pure Cow count
    cows -= bulls
    
    return f"{bulls}A{cows}B"

# Example usage:
# print(getHint("1807", "7810"))  -> Output: "1A3B"

Edge Cases Handled

  • No Matches: If secret and guess share no digits, frequency counts will be disjoint or zero. Sum of mins is 0, Bulls=0, Cows=0. Correctly returns "0A0B".
  • All Digits Match (Permutation): E.g., S=“123”, G=“321”. Frequencies match exactly. sum(min) = length(N). Bulls will be 0 (assuming no fixed points). Cows = N - 0 = N. Correctly returns "0ANB".
  • Duplicate Digits: E.g., S=“11”, G=“12”.
    • FreqS: {1:2}, FreqG: {1:1, 2:1}. Min sum for ‘1’ is 1. Bulls=0 (indices don’t match). Cows = 1 - 0 = 1? Wait. S=“11”, G=“12”. Index 0 matches (‘1’). Bull=1. FreqS={1:2}, FreqG={1:1, 2:1}. Min sum for ‘1’ is min(2,1)=1. Total Matches = 1. Cows = 1 - 1 (Bull) = 0? Wait.
    • Let’s re-verify S=“11”, G=“12”.
      • Index 0: ‘1’==‘1’. Bull=1.
      • FreqS={1:2}, FreqG={1:1, 2:1}. Min sum = min(2,1) for digit 1 + others (min is 0). Total Matches = 1.
      • Cows = 1 - 1 = 0. Correct? S=“11”, G=“12”. One ‘1’ matches at pos 0. The other ‘1’ in secret has no match in guess (guess only has one ‘1’). So yes, 0 cows is correct.
    • Example: S=“1807”, G=“7810” -> Bulls=1 (‘8’), Cows=3.
      • FreqS={1:1,8:1,0:1,7:1}, FreqG={7:1,8:1,1:1,0:1}. Min sum = 4 (all digits match once). Bulls=1. Cows=3. Correct.
  • Single Character: Handled by loop ranges correctly returning “0A0B” or “1A0B”.