Question

2086. Minimum Number of Food Buckets to Feed the Hamsters

中文文档

Description

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:

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

Solutions

Solution 1

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

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;
  }
}

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;
  }
};

func minimumBuckets(street string) int {
  ans, n := 0, len(street)
  for i := 0; i < n; i++ {
    if street[i] == 'H' {
      if i+1 < n && street[i+1] == '.' {
        ans++
        i += 2
      } else if i > 0 && street[i-1] == '.' {
        ans++
      } else {
        return -1
      }
    }
  }
  return ans
}