299. Bulls and Cows
Explanation
To solve this problem, we can iterate through the secret and guess strings simultaneously and count the bulls and cows based on the matching digits. While counting the bulls, we mark the positions of those digits to avoid counting them as cows later. For counting cows, we use a hashmap to store the frequency of digits in the secret. We decrement the frequency for each digit that matches in the guess string. If the frequency is greater than 0, it means that digit is a cow. Finally, we construct the result string in the format "xAyB" where x is the number of bulls and y is the number of cows.
- Initialize variables to count bulls, cows, and a hashmap to store the frequency of digits in secret.
- Iterate through the strings secret and guess simultaneously.
- If the digits at the same index are the same, increment the bulls count and mark the position.
- Otherwise, increment the frequency of the digit in secret in the hashmap.
- Iterate through the guess string.
- If the digit is in the hashmap and its frequency is greater than 0, increment cows count and decrement the frequency.
- Construct the result string and return.
Time Complexity: O(n) where n is the length of the input strings (secret and guess). Space Complexity: O(1) due to the constant size of the hashmap storing digit frequencies.
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0, cows = 0;
int[] digits = new int[10];
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
bulls++;
} else {
digits[secret.charAt(i) - '0']++;
}
}
for (int i = 0; i < guess.length(); i++) {
if (secret.charAt(i) != guess.charAt(i) && digits[guess.charAt(i) - '0'] > 0) {
cows++;
digits[guess.charAt(i) - '0']--;
}
}
return bulls + "A" + cows + "B";
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.