Minimum number of food buckets to feed the hamsters

String Dynamic Programming Greedy

48.0% acceptance

Feb 25, 2026

572

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. 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_buckets(hamsters: String) -> i32 {
    let h: Vec<u8> = hamsters.bytes().collect();
    let n = h.len();
    let mut count = 0;
    let mut buckets = vec![false; n]; // tracks placed buckets

    for i in 0..n {
      if h[i] != b'H' {
        continue;
      }
      // Check if already fed by a bucket to the left
      if i > 0 && buckets[i - 1] {
        continue;
      }
      // Try placing bucket to the right
      if i + 1 < n && h[i + 1] == b'.' {
        buckets[i + 1] = true;
        count += 1;
      } else if i > 0 && h[i - 1] == b'.' {
        // Try placing bucket to the left
        buckets[i - 1] = true;
        count += 1;
      } else {
        return -1;
      }
    }

    count
  }
}