2086. Minimum Number of Food Buckets to Feed the Hamsters LeetCode Solution
In this guide, you will get 2086. Minimum Number of Food Buckets to Feed the Hamsters LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Food Buckets to Feed the Hamsters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Food Buckets to Feed the Hamsters
You are given a 0-indexed string hamsters where hamsters[i] is either:
‘H’ indicating that there is a hamster at index i, or
‘.’ indicating that index i is empty.
You will add some number of food buckets at the empty indices in order to feed the hamsters. A hamster can be fed if there is at least one food bucket to its left or to its right. More formally, a hamster at index i can be fed if you place a food bucket at index i – 1 and/or at index i + 1.
Return the minimum number of food buckets you should place at empty indices to feed all the hamsters or -1 if it is impossible to feed all of them.
Input: hamsters = “H..H”
Output: 2
Explanation: We place two food buckets at indices 1 and 2.
It can be shown that if we place only one food bucket, one of the hamsters will not be fed.
Example 2:
Input: hamsters = “.H.H.”
Output: 1
Explanation: We place one food bucket at index 2.
Example 3:
Input: hamsters = “.HHH.”
Output: -1
Explanation: If we place a food bucket at every empty index as shown, the hamster at index 2 will not be able to eat.
Constraints:
1 <= hamsters.length <= 105
hamsters[i] is either'H' or '.'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2086. Minimum Number of Food Buckets to Feed the Hamsters LeetCode Solution in C++
class Solution {
public:
int minimumBuckets(string street) {
for (int i = 0; i < street.length(); ++i)
if (street[i] == 'H') {
if (i > 0 && street[i - 1] == 'B')
continue;
if (i + 1 < street.length() && street[i + 1] == '.')
// Always prefer place a bucket in (i + 1) because it enhances the
// possibility to collect the upcoming houses.
street[i + 1] = 'B';
else if (i > 0 && street[i - 1] == '.')
street[i - 1] = 'B';
else
return -1;
}
return ranges::count(street, 'B');
}
}; /* code provided by PROGIEZ */
2086. Minimum Number of Food Buckets to Feed the Hamsters LeetCode Solution in Java
class Solution {
public int minimumBuckets(String street) {
final char[] A = street.toCharArray();
for (int i = 0; i < A.length; ++i)
if (A[i] == 'H') {
if (i > 0 && A[i - 1] == 'B')
continue;
if (i + 1 < A.length && A[i + 1] == '.')
// Always prefer place a bucket in (i + 1) because it enhances the
// possibility to collect the upcoming houses.
A[i + 1] = 'B';
else if (i > 0 && A[i - 1] == '.')
A[i - 1] = 'B';
else
return -1;
}
return (int) new String(A).chars().filter(a -> a == 'B').count();
}
} // code provided by PROGIEZ
2086. Minimum Number of Food Buckets to Feed the Hamsters LeetCode Solution in Python
class Solution:
def minimumBuckets(self, street: str) -> int:
A = list(street)
for i, c in enumerate(A):
if c == 'H':
if i > 0 and A[i - 1] == 'B':
continue
if i + 1 < len(A) and A[i + 1] == '.':
# Always prefer place a bucket in (i + 1) because it enhances the
# possibility to collect the upcoming houses.
A[i + 1] = 'B'
elif i > 0 and A[i - 1] == '.':
A[i - 1] = 'B'
else:
return -1
return A.count('B') # code by PROGIEZ
