LeetCode 299: Bulls and Cows Solution in Python – A Step-by-Step Guide

What Is LeetCode 299: Bulls and Cows?

In LeetCode 299: Bulls and Cows, you’re given two strings: secret (the hidden number) and guess (your guess), both of the same length and made of digits (0-9). Your task is to return a hint in the format "xAyB," where:

• x (bulls) is the count of digits that match in both value and position.
• y (cows) is the count of digits that are in secret but in the wrong position in guess.

For example, secret = "1807", guess = "7810" gives "1A3B" (1 bull: 8; 3 cows: 0, 1, 7). This problem tests your string and counting skills, sharing a vibe with LeetCode 290: Word Pattern.

Problem Statement

• Input: Two strings secret and guess.
• Output: A string "xAyB" (x = bulls, y = cows).
• Rules: Bulls are exact matches; cows are misplaced matches; same length; digits only.

Constraints

• Length: 1 to 1000.
• Characters: Digits 0-9.
• secret and guess are same length.

Examples

• Input: secret = "1807", guess = "7810"
• Output: "1A3B"
• Input: secret = "1123", guess = "0111"
• Output: "1A1B"
• Input: secret = "1", guess = "0"
• Output: "0A0B"

Understanding the Problem: Cracking the Hint

To solve LeetCode 299: Bulls and Cows in Python, we need to compare secret and guess, count bulls (exact matches), and then figure out cows (digits in secret but misplaced in guess). For "1807" and "7810":

• Bulls: 8 matches at position 2 → 1 bull.
• Cows: 7, 1, 0 are in secret but not in the right spots → 3 cows.
• Result: "1A3B".

A naive way might double-count bulls as cows, so we need to be careful. We’ll use:

• Best Solution (Hash Map with Single Pass): O(n) time, O(1) space—fast and sleek.
• Alternative Solution (Two-Pass Approach): O(n) time, O(1) space—simpler but split.

Let’s dive into the hash map solution with a friendly breakdown that’s easy to follow.

Best Solution: Hash Map with Single Pass

Why This Is the Best Solution

The hash map with single-pass approach is the top choice for LeetCode 299 because it’s efficient—O(n) time, O(1) space (since digits are 0-9, a fixed-size map)—and does everything in one go. It counts bulls and tracks unmatched digits in a hash map, cleverly pairing them for cows without a second pass. It’s like playing the game with a single scorecard—quick and smart!

How It Works

Let’s imagine this like scoring a guess:

• Step 1: Set Up Counters:
• Bulls = 0 (exact matches).
• Cows = 0 (misplaced matches).
• Hash map to track digits (0-9) we haven’t matched yet.
• Step 2: One Pass Through Both Strings:
• For each position i in secret and guess:
• If secret[i] = guess[i], it’s a bull—add 1, skip to next.
• If not:
• If guess[i] was in secret earlier (map > 0), it’s a cow—add 1, reduce map.
• If secret[i] is unmatched, add it to map (or increase count).
• Step 3: Build the Hint:
• Return "bullsAcowsB" as a string.
• Step 4: Why It Works:
• Bulls are caught first, avoiding double-counting.
• Map tracks unpaired digits, pairing them as cows when they show up later.
• Single pass keeps it fast.

It’s like a quick tally—check matches, then pair the rest!

Step-by-Step Example

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

• Init: bulls = 0, cows = 0, map = {}.
• Position 0: '1' vs '7':
• No match.
• map['1'] = 1 (secret unpaired).
• map['7'] = -1 (guess unpaired, negative for guess).
• Position 1: '8' vs '8':
• Match! bulls = 1.
• Position 2: '0' vs '1':
• No match.
• map['1'] = 1 - 1 = 0 (guess '1' pairs with earlier secret '1', cows = 1).
• map['0'] = 1 (secret unpaired).
• Position 3: '7' vs '0':
• No match.
• map['7'] = -1 + 1 = 0 (secret '7' pairs with earlier guess '7', cows = 2).
• map['0'] = 1 - 1 = 0 (guess '0' pairs with earlier secret '0', cows = 3).
• Result: bulls = 1, cows = 3 → "1A3B".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def getHint(self, secret: str, guess: str) -> str:
        # Step 1: Set up counters and map
        bulls = 0
        cows = 0
        digits = {}  # Map for unmatched digits

        # Step 2: One pass through both strings
        for s, g in zip(secret, guess):  # Pair chars together
            if s == g:  # Exact match
                bulls += 1
            else:
                # Check guess digit for cow from secret
                if s in digits and digits[s] > 0:  # Secret had it unpaired
                    cows += 1
                    digits[s] -= 1  # Pair it up
                else:
                    digits[g] = digits.get(g, 0) - 1  # Guess unpaired (negative)

                # Check secret digit for cow from guess
                if g in digits and digits[g] < 0:  # Guess had it unpaired
                    cows += 1
                    digits[g] += 1  # Pair it up
                else:
                    digits[s] = digits.get(s, 0) + 1  # Secret unpaired (positive)

        # Step 3: Build the hint
        return f"{bulls}A{cows}B"

• Line 4-6: Initialize bulls, cows, and an empty hash map for digits.
• Line 9-20: Loop through secret and guess together:
• Line 10-11: If chars match, increment bulls.
• Line 12-20: If no match:
• Line 13-15: If secret digit s is in map and positive (unpaired from secret), it’s a cow—reduce count.
• Line 16-17: Else, mark guess digit g as unpaired (negative in map).
• Line 18-20: If guess digit g is in map and negative (unpaired from guess), it’s a cow—increase count; else mark secret digit s as unpaired (positive).
• Line 22: Return hint as "xAyB".

• Time Complexity: O(n)—one pass through strings.
• Space Complexity: O(1)—map size is fixed (10 digits).

This is like a quick scorecard—tally and match in one go!

Alternative Solution: Two-Pass Approach

Why an Alternative Approach?

The two-pass approach splits bulls and cows into separate steps—O(n) time, O(1) space. It’s simpler to follow, counting bulls first and then cows with a map, like doing the game in two rounds—less clever but easier to grasp.

How It Works

Let’s think of this as a two-step guess:

• Step 1: Count bulls by comparing positions.
• Step 2: Use a map to count secret digits, subtract bulls, then find cows in guess.
• Step 3: Build hint.

It’s like checking exact hits, then searching for strays!

Step-by-Step Example

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

• Pass 1: Bulls:
• 1 vs 7: No.
• 8 vs 8: Yes, bulls = 1.
• 0 vs 1: No.
• 7 vs 0: No.
• bulls = 1.
• Pass 2: Cows:
• Map: {'1': 1, '8': 1, '0': 1, '7': 1}.
• Subtract bulls: {'1': 1, '8': 0, '0': 1, '7': 1}.
• Guess: '7' (cow, map['7'] -= 1), '8' (bull, skip), '1' (cow, map['1'] -= 1), '0' (cow, map['0'] -= 1).
• cows = 3.
• Result: "1A3B".

Code for Two-Pass Approach

Copy codeclass Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = 0
        cows = 0
        secret_map = {}

        # Pass 1: Count bulls
        for s, g in zip(secret, guess):
            if s == g:
                bulls += 1
            else:
                secret_map[s] = secret_map.get(s, 0) + 1

        # Pass 2: Count cows
        for i in range(len(secret)):
            s, g = secret[i], guess[i]
            if s != g and g in secret_map and secret_map[g] > 0:
                cows += 1
                secret_map[g] -= 1

        return f"{bulls}A{cows}B"

• Time Complexity: O(n)—two passes.
• Space Complexity: O(1)—fixed map.

It’s a clear two-step check!

Comparing the Two Solutions

• Hash Map Single Pass (Best):
• Pros: O(n) time, O(1) space, one pass.
• Cons: Slightly trickier logic.
• Two-Pass (Alternative):
• Pros: O(n) time, O(1) space, simpler steps.
• Cons: Two passes, less elegant.

Single pass wins for speed.

Additional Examples and Edge Cases

• "11", "11": "2A0B".
• "123", "321": "0A3B".
• "1", "1": "1A0B".

Single pass is faster.

Complexity Breakdown

• Single Pass: Time O(n), Space O(1).
• Two-Pass: Time O(n), Space O(1).

Single pass rules.

Key Takeaways

• Single Pass: One sweep—smart!
• Two-Pass: Step-by-step—clear!
• Games: Counting is fun.
• Python Tip: Dictionaries rock—see [Python Basics](/python/basics).

Final Thoughts: Crack the Code

LeetCode 299: Bulls and Cows in Python is a playful number puzzle. The single-pass hash map nails it fast, while two-pass keeps it simple. Want more? Try LeetCode 290: Word Pattern or LeetCode 205: Isomorphic Strings. Ready to guess? Head to Solve LeetCode 299 on LeetCode and crack that hint today!