# Minimum Number of Food Buckets to Feed the Hamsters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-food-buckets-to-feed-the-hamsters)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-food-buckets-to-feed-the-hamsters
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Grab](https://scaleengineer.com/companies/grab), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Geico](https://scaleengineer.com/companies/geico)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-number-of-food-buckets-to-feed-the-hamsters/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-number-of-food-buckets-to-feed-the-hamsters/image1.png) 

**Input:** hamsters = ".H.H."
**Output:** 1
**Explanation:** We place one food bucket at index 2.

**Example 3:**

![](https://assets.glich.co/dsa/minimum-number-of-food-buckets-to-feed-the-hamsters/image2.png) 

**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 `'.'`.

# Approaches
## Greedy Approach with Auxiliary Array
This approach employs a greedy strategy by iterating through the hamsters and placing buckets as needed. To keep track of where buckets are placed and which hamsters are consequently fed, it uses an auxiliary character array. This makes the logic for checking the status of adjacent spots straightforward but comes at the cost of additional memory.
**Time:** O(N), where N is the length of the input string. We perform a single pass through the array. · **Space:** O(N), where N is the length of the input string. This is due to the creation of a character array to store the state of buckets.
**Pros:** The logic is very explicit and easy to reason about, as the state of placed buckets is clearly maintained in the auxiliary array.
**Cons:** Requires extra space proportional to the length of the input string, which can be significant for large inputs.
### Explanation
The core idea is to make a local optimal choice at each step, which leads to a global optimum. We iterate from left to right. When we encounter a hamster 'H', we first check if a bucket placed for a previous hamster already feeds it. If not, we need to place a new bucket. The best greedy move is to place the bucket to the right of the current hamster (at index `i+1`) if possible. This is because a bucket at `i+1` not only feeds the hamster at `i` but also has the potential to feed a future hamster at `i+2`, maximizing its utility. If we cannot place a bucket to the right, our only other option is to place it to the left (at `i-1`). If neither spot is available, the task is impossible. We use a character array, a copy of the input string, to mark the locations of placed buckets (e.g., with a 'B'), which simplifies state tracking.

```java
class Solution {
    public int minimumBuckets(String hamsters) {
        char[] chars = hamsters.toCharArray();
        int n = chars.length;
        int buckets = 0;
        for (int i = 0; i < n; i++) {
            if (chars[i] == 'H') {
                // Check if already fed by a bucket on the left
                if (i > 0 && chars[i - 1] == 'B') {
                    continue;
                }

                // Try to place a bucket to the right (greedy choice)
                if (i + 1 < n && chars[i + 1] == '.') {
                    buckets++;
                    chars[i + 1] = 'B'; // Mark the bucket
                } 
                // Else, try to place a bucket to the left
                else if (i - 1 >= 0 && chars[i - 1] == '.') {
                    buckets++;
                    chars[i - 1] = 'B'; // Mark the bucket
                } 
                // Impossible to feed this hamster
                else {
                    return -1;
                }
            }
        }
        return buckets;
    }
}
```
### Algorithm
- Convert the input string `hamsters` into a character array `chars` to allow for modification.
- Initialize a counter for buckets, `buckets = 0`.
- Iterate through the character array from left to right with an index `i`.
- If `chars[i]` is a hamster ('H'):
  - First, check if this hamster has already been fed by a bucket placed to its left. This would be the case if `i > 0` and `chars[i-1]` has been marked as a bucket (e.g., 'B'). If so, `continue` to the next position.
  - If the hamster is not fed, we must place a bucket. The greedy choice is to place it to the right. If `i + 1` is a valid index and `chars[i + 1]` is an empty spot ('.'), increment `buckets` and update `chars[i + 1]` to 'B' to mark that a bucket has been placed.
  - If placing a bucket on the right is not possible, we must try to place it on the left. If `i - 1` is a valid index and `chars[i - 1]` is an empty spot ('.'), increment `buckets` and update `chars[i - 1]` to 'B'.
  - If neither the left nor the right side has an empty spot, it's impossible to feed this hamster. Return -1.
- After the loop completes, return the total `buckets` count.

## Optimized Greedy Approach with Constant Space
This is the most efficient approach, solving the problem in a single pass with constant extra space. It uses the same greedy principle as the previous method but avoids the O(N) space complexity by cleverly manipulating the loop index instead of using an auxiliary array to track state. The core idea remains: when feeding a hamster, always prioritize placing a bucket to its right to maximize its coverage.
**Time:** O(N), where N is the length of the input string. Although we sometimes jump the index, we still visit each character at most a constant number of times. · **Space:** O(1). We only use a few variables to store the count and the loop index, which does not depend on the input size.
**Pros:** Extremely efficient in terms of memory, using only a constant amount of extra space.; Achieves the optimal time complexity with a single pass.
**Cons:** The logic involving the loop index jump (`i += 2`) can be slightly less intuitive to understand at first glance compared to explicitly marking buckets in an array.
### Explanation
This optimized solution refines the greedy strategy to work in-place without needing an extra array. We iterate through the string, and upon finding a hamster at index `i`, we decide where to place a bucket. The best choice is always `i+1` if it's empty. By placing a bucket at `i+1`, we feed the hamster at `i` and potentially one at `i+2`. The key insight is that we can account for this by skipping the next two indices in our loop. We do this by advancing `i` by 2. The loop's own increment will then take over, effectively moving our focus to `i+3`. This prevents double-counting buckets or re-evaluating an already-fed hamster. If `i+1` is not a valid spot, we check `i-1`. Since we are iterating left-to-right, checking `hamsters.charAt(i-1)` is sufficient; we don't need to worry about whether a bucket was already placed there, because our `i+=2` jump logic would have skipped over `i` if a bucket at `i-1` had been placed for a hamster at `i-2`. This makes the logic work with O(1) space.

```java
class Solution {
    public int minimumBuckets(String hamsters) {
        int n = hamsters.length();
        int buckets = 0;
        for (int i = 0; i < n; ++i) {
            if (hamsters.charAt(i) == 'H') {
                // Try to place a bucket to the right (greedy choice)
                if (i + 1 < n && hamsters.charAt(i + 1) == '.') {
                    buckets++;
                    // This bucket covers hamsters at i and i+2.
                    // Skip the next two positions.
                    i += 2;
                } 
                // Else, try to place a bucket to the left
                else if (i - 1 >= 0 && hamsters.charAt(i - 1) == '.') {
                    buckets++;
                } 
                // Impossible to feed this hamster
                else {
                    return -1;
                }
            }
        }
        return buckets;
    }
}
```
### Algorithm
- Initialize a counter for buckets, `buckets = 0`.
- Iterate through the `hamsters` string using an index `i` from `0` to `n-1`.
- If the character at `i` is a hamster ('H'):
  - We apply our greedy strategy. First, check if we can place a bucket to the right. If `i + 1` is within bounds and `hamsters.charAt(i + 1)` is an empty spot ('.'), this is the optimal move. Increment `buckets` and advance the loop index `i` by 2. This jump is crucial: it skips over the position where the bucket was placed (`i+1`) and the next position (`i+2`), as any hamster there would be fed by this new bucket.
  - If placing a bucket to the right is not possible, we check the left. If `i - 1` is within bounds and `hamsters.charAt(i - 1)` is an empty spot ('.'), we must place a bucket there. Increment `buckets`. No index jump is needed here.
  - If neither the right nor the left spot is available for a bucket, it's impossible to feed the hamster. Return -1.
- If the character at `i` is an empty spot ('.'), we simply let the loop increment `i` to move to the next position.
- After the loop finishes, return the total `buckets` count.

# Solutions
### Java

```java
class Solution { public int minimumBuckets ( String street ) { int n = street . length (); int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( street . charAt ( i ) == 'H' ) { if ( i + 1 < n && street . charAt ( i + 1 ) == '.' ) { ++ ans ; i += 2 ; } else if ( i > 0 && street . charAt ( i - 1 ) == '.' ) { ++ ans ; } else { return - 1 ; } } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int minimumBuckets(string street) {
    int n = street.size();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (street[i] == 'H') {
        if (i + 1 < n && street[i + 1] == '.') {
          ++ans;
          i += 2;
        } else if (i && street[i - 1] == '.') {
          ++ans;
        } else {
          return -1;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def minimumBuckets ( self , street : str ) -> int : ans = 0 i , n = 0 , len ( street ) while i < n : if street [ i ] == 'H' : if i + 1 < n and street [ i + 1 ] == '.' : i += 2 ans += 1 elif i and street [ i - 1 ] == '.' : ans += 1 else : return - 1 i += 1 return ans
```