299. Bulls and Cows

Description

The problem involves a game where you are given two strings: secret and guess, both of the same length. You need to provide a hint that includes:

• The number of "bulls" (correct digits in the correct positions).
• The number of "cows" (correct digits but in the wrong positions).

The output should be a string formatted as "xAyB", where x is the number of bulls and y is the number of cows.

Intuition

To solve this problem, we need to distinguish between two scenarios:

1. A digit in guess exactly matches the corresponding digit in secret (a bull).
2. A digit in guess is in secret but in the wrong position (a cow).

By counting bulls first and then handling cows based on the frequency of unmatched digits, we can efficiently compute the desired hint.

Approach

1. Initialize counters: Start with bulls = 0, cows = 0, and an array raj of size 10 to keep track of the frequency of digits that have been encountered but not matched as bulls.
2. Iterate through the strings: For each character in the strings: - If the digits in secret and guess match, increment the bulls counter. - If they don't match, update the raj array: - If the current digit in secret was previously encountered in guess, it means we have found a cow, so increment the cows counter. - If the current digit in guess was previously encountered in secret, increment the cows counter. - Update the raj array to reflect the current unmatched digits.
3. Return the result: Format the result as "xAyB" where x is the number of bulls and y is the number of cows.

Complexity

Time Complexity:

O(n), where n is the length of the strings secret and guess. We iterate through the strings once, making the solution linear in time.

Space Complexity:

O(1). The raj array is of fixed size (10), and no additional space is used that scales with the input size.

Code

C++

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0;
        int cows = 0;
        vector raj(10, 0);

        for (int i = 0; i < secret.length(); i++) {
            int sec = secret[i] - '0';
            int gu = guess[i] - '0';

            if (sec == gu) {
                bulls++;
                continue;
            }
            if (raj[sec] < 0) {
                cows++;
            }
            if (raj[gu] > 0) {
                cows++;
            }
            raj[sec]++;
            raj[gu]--;
        }

        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

Python

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = 0
        cows = 0
        raj = [0] * 10

        for i in range(len(secret)):
            sec = int(secret[i])
            gu = int(guess[i])

            if sec == gu:
                bulls += 1
                continue
            if raj[sec] < 0:
                cows += 1
            if raj[gu] > 0:
                cows += 1
            raj[sec] += 1
            raj[gu] -= 1

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

Java

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        int[] raj = new int[10];

        for (int i = 0; i < secret.length(); i++) {
            int sec = Character.getNumericValue(secret.charAt(i));
            int gu = Character.getNumericValue(guess.charAt(i));

            if (sec == gu) {
                bulls++;
                continue;
            }
            if (raj[sec] < 0) {
                cows++;
            }
            if (raj[gu] > 0) {
                cows++;
            }
            raj[sec]++;
            raj[gu]--;
        }

        return bulls + "A" + cows + "B";
    }
}

JavaScript

/**
 * @param {string} sec
 * @param {string} guess
 * @return {string}
 */
var getHint = function (sec, guess) {

    let bulls = 0;

    let cows = 0;

    let raj = Array(10).fill(0);

    for (let i = 0; i < sec.length; i++) {

        let gu = parseInt(guess[i]);

        let secret = parseInt(sec[i]);

        if (secret === gu) {
            bulls++;
            continue;
        }
        if (raj[secret] < 0) {
            cows++;
        }
        if (raj[gu] > 0) {
            cows++;
        }
        raj[secret]++;
        raj[gu]--;
    }
    return (`${bulls}A${cows}B`);

};