</>Ali · LeetCode
#0299·MediumStrings

Bulls and Cows

LeetCode #299 · Medium · Strings · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Two-Pass Counting Over Non-Bull Digits

Key insight

A cow is a guess digit that has a *non-bull* match left over in the secret. If we count digit frequencies of the secret only at positions where it disagrees with the guess, then walking the guess a second time and consuming from that counter is exactly the right thing — bulls never enter the counter, so they can't be double-counted as cows.

Strategy

  1. 1Pass 1: for each index where secret[i] != guess[i], increment
  2. 2Pass 2: walk both strings together.
  3. 3Format the result as "<a>A<b>B".
Time
O(n)
two linear passes over strings of length n.
Space
O(1)
the frequency array has a fixed size of 10.
Problem description(from LeetCode)

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: - The number of "bulls": digits in the guess that are in the correct position. - The number of "cows": digits in the guess that exist in the secret but are in the wrong position. Specifically, non-bull digits of the guess that could be rearranged to become bulls. Return the hint formatted as "xAyB", where x is the number of bulls and y is the number of cows. Both strings may contain duplicate digits.

Examples

Example 1
Input:
secret = "1807", guess = "7810"
Output:
"1A3B"
Example 2
Input:
secret = "1123", guess = "0111"
Output:
"1A1B"
Note:
Only one of the two unmatched 1s in the guess counts as a cow, because there is only one non-bull 1 left in the secret to pair with.

Constraints

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

C++ Solution

solution.cpp
class Solution {
public:
string getHint(string secret, string guess) {
    int a = 0, b = 0;
    vector<int> count = vector<int>(10, 0);

    for (int i = 0; i < secret.size(); i++)
      if (secret[i] != guess[i]) count[secret[i] - '0']++;

    for (int i = 0; i < secret.size(); i++) {
      int s = secret[i] - '0';
      int g = guess[i] - '0';
      if (s == g) a++;
      else if (count[g] > 0) {
        count[g]--;
        b++;
      }
    }

    return to_string(a) + 'A' + to_string(b) + 'B';
  }
};

More Strings problems