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 shouldplace at empty indices to feed all the hamsters or _-1 if it is impossible to feed all of them.

Examples

Example 1

1
2
3
4
5
6
7


![](https://assets.leetcode.com/uploads/2022/11/01/example1.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

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2022/11/01/example2.png)

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

Example 3

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2022/11/01/example3.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 <= 10^5
  • hamsters[i] is either'H' or '.'.

Solution

Method 1 – Greedy Placement

Intuition

To minimize buckets, we should place a bucket to the right of each hamster if possible, otherwise to the left. If neither is possible, it’s impossible to feed all hamsters.

Approach

  1. Iterate through the string.
  2. For each hamster at index i:
    • If the right cell is empty and not already used, place a bucket at i+1.
    • Else if the left cell is empty and not already used, place a bucket at i-1.
    • Else, return -1 (impossible).
  3. Track bucket placements to avoid double counting.
  4. Return the total number of buckets placed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int minimumBuckets(string hamsters) {
        int n = hamsters.size(), ans = 0;
        vector<bool> bucket(n, false);
        for (int i = 0; i < n; ++i) {
            if (hamsters[i] == 'H') {
                if (i+1 < n && hamsters[i+1] == '.' && !bucket[i+1]) {
                    bucket[i+1] = true;
                    ans++;
                } else if (i-1 >= 0 && hamsters[i-1] == '.' && !bucket[i-1]) {
                    bucket[i-1] = true;
                    ans++;
                } else {
                    return -1;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func minimumBuckets(hamsters string) int {
    n := len(hamsters)
    bucket := make([]bool, n)
    ans := 0
    for i := 0; i < n; i++ {
        if hamsters[i] == 'H' {
            if i+1 < n && hamsters[i+1] == '.' && !bucket[i+1] {
                bucket[i+1] = true
                ans++
            } else if i-1 >= 0 && hamsters[i-1] == '.' && !bucket[i-1] {
                bucket[i-1] = true
                ans++
            } else {
                return -1
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int minimumBuckets(String hamsters) {
        int n = hamsters.length(), ans = 0;
        boolean[] bucket = new boolean[n];
        for (int i = 0; i < n; ++i) {
            if (hamsters.charAt(i) == 'H') {
                if (i+1 < n && hamsters.charAt(i+1) == '.' && !bucket[i+1]) {
                    bucket[i+1] = true;
                    ans++;
                } else if (i-1 >= 0 && hamsters.charAt(i-1) == '.' && !bucket[i-1]) {
                    bucket[i-1] = true;
                    ans++;
                } else {
                    return -1;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun minimumBuckets(hamsters: String): Int {
        val n = hamsters.length
        val bucket = BooleanArray(n)
        var ans = 0
        for (i in 0 until n) {
            if (hamsters[i] == 'H') {
                if (i+1 < n && hamsters[i+1] == '.' && !bucket[i+1]) {
                    bucket[i+1] = true
                    ans++
                } else if (i-1 >= 0 && hamsters[i-1] == '.' && !bucket[i-1]) {
                    bucket[i-1] = true
                    ans++
                } else {
                    return -1
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        n: int = len(hamsters)
        bucket: list[bool] = [False] * n
        ans: int = 0
        for i in range(n):
            if hamsters[i] == 'H':
                if i+1 < n and hamsters[i+1] == '.' and not bucket[i+1]:
                    bucket[i+1] = True
                    ans += 1
                elif i-1 >= 0 and hamsters[i-1] == '.' and not bucket[i-1]:
                    bucket[i-1] = True
                    ans += 1
                else:
                    return -1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn minimum_buckets(hamsters: String) -> i32 {
        let n = hamsters.len();
        let mut bucket = vec![false; n];
        let mut ans = 0;
        let bytes = hamsters.as_bytes();
        for i in 0..n {
            if bytes[i] == b'H' {
                if i+1 < n && bytes[i+1] == b'.' && !bucket[i+1] {
                    bucket[i+1] = true;
                    ans += 1;
                } else if i > 0 && bytes[i-1] == b'.' && !bucket[i-1] {
                    bucket[i-1] = true;
                    ans += 1;
                } else {
                    return -1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    minimumBuckets(hamsters: string): number {
        const n = hamsters.length;
        const bucket = new Array(n).fill(false);
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            if (hamsters[i] === 'H') {
                if (i+1 < n && hamsters[i+1] === '.' && !bucket[i+1]) {
                    bucket[i+1] = true;
                    ans++;
                } else if (i-1 >= 0 && hamsters[i-1] === '.' && !bucket[i-1]) {
                    bucket[i-1] = true;
                    ans++;
                } else {
                    return -1;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we process each character once.
  • 🧺 Space complexity: O(n), for the bucket array.