MediumNo. 0299

Bulls and Cows — LeetCode 299 Python Solution

Pattern
Hash Map
Topics
Hash Table, String, Counting
Reading time
2 min

The 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.

Example

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

Python solution

PythonSolution
class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        cnt1, cnt2 = Counter(), Counter()
        x = 0
        for a, b in zip(secret, guess):
            if a == b:
                x += 1
            else:
                cnt1[a] += 1
                cnt2[b] += 1
        y = sum(min(cnt1[c], cnt2[c]) for c in cnt1)
        return f"{x}A{y}B"

Complexity

Time
O(n), where n is the length of the secret number and the friend's guess
Space · auxiliary
O(|Σ|), where |Σ| is the size of the character set

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 299. Bulls and Cows is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0383Ransom NoteEasy
0387First Unique Character in a StringEasy
0451Sort Characters By FrequencyMedium
0692Top K Frequent WordsMedium
0767Reorganize StringMedium
0811Subdomain Visit CountMedium

Frequently asked questions

How hard is LeetCode 299. Bulls and Cows?

LeetCode 299. Bulls and Cows is rated Medium on LeetCode.

What is the time complexity of LeetCode 299. Bulls and Cows?

The Python solution on this page runs in O(n), where n is the length of the secret number and the friend's guess.

What is the space complexity of LeetCode 299. Bulls and Cows?

The Python solution on this page uses O(|Σ|), where |\Sigma| is the size of the character set auxiliary space.

What topics does LeetCode 299. Bulls and Cows cover?

LeetCode 299. Bulls and Cows is tagged Hash Table, String and Counting on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.