Bulls and Cows

Problem Statement

In the "Bulls and Cows" game, you have a hidden number called the 'secret' and your friend tries to guess this number. After each guess, your responsibility is to provide feedback in the form of hints about how close their guess was to the secret. The feedback comprises two types of hints: "bulls" and "cows." Bulls indicate the number of digits in the guess that are both correct in value and positioned correctly in relation to the secret. On the other hand, cows represent the number of digits that are correct in value but positioned incorrectly. The challenge lies not just in counting these bulls and cows but also ensuring that a digit from the guess can only be used once, which becomes non-trivial when duplicates are involved. The expected output is a format of "xAyB" where x represents the bulls and y represents the cows.

Examples

Example 1

Input:

secret = "1807", guess = "7810"

Output:

"1A3B"

Explanation:

Bulls are connected with a '|' and cows are underlined:
"1807"
|
"7810"

Example 2

Input:

secret = "1123", guess = "0111"

Output:

"1A1B"

Explanation:

Bulls are connected with a '|' and cows are underlined:
"1123" "1123"
| or |
"0111" "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.

Constraints

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

Approach and Intuition

The task involves string manipulation and a clear understanding of how to compare positions of characters in two strings (the secret and the guess). Below is a step-by-step breakdown on how to derive the solution:

1. Initialize counters for bulls and cows to zero.

2. First, iterate through the secret and guess at the same index. If a character in secret is the same as in guess at the same index, increase the bull counter and record this index as checked so that these characters aren't reconsidered for cows.

3. Use a hash map or array to keep track of the frequencies of each character in secret that wasn't a bull. This helps in efficiently checking which characters in guess (that aren't bulls) can actually be considered as cows.

4. For each character in guess that wasn't already counted as a bull, check if it can be a cow by looking it up in the hash map or array. If it's a non-bull character and exists in the map, it means this character is in the wrong position but is indeed in secret, so increase the cow counter and decrease the count in the map.

5. Iterate through to check all characters, adjust counts in each step to ensure no character is double-counted as both bull and cow.

This method overall checks direct matches first (bulls) and then leverages frequency counts to correctly allocate cows, ensuring to handle duplicates accurately by managing counters for each digit. The use of a tracking counter for bulls and a map for managing potential cows provides a robust way to handle the game's constraints and provide accurate feedback.

Solutions

class Solution {
    public String calculateHint(String secret, String guess) {
        HashMap<Character, Integer> mapCounter = new HashMap<>();
            
        int bullsCount = 0, cowsCount = 0;
        int length = guess.length();
        for (int i = 0; i < length; ++i) {
            char charSecret = secret.charAt(i);
            char charGuess = guess.charAt(i);
            if (charSecret == charGuess) {
                bullsCount++;    
            } else {
                if (mapCounter.getOrDefault(charSecret, 0) < 0) 
                    cowsCount++;
                if (mapCounter.getOrDefault(charGuess, 0) > 0)
                    cowsCount++;
                mapCounter.put(charSecret, mapCounter.getOrDefault(charSecret, 0) + 1);
                mapCounter.put(charGuess, mapCounter.getOrDefault(charGuess, 0) - 1);
            }
        } 
                    
        return Integer.toString(bullsCount) + "A" + Integer.toString(cowsCount) + "B";
    }
}