minimum-number-of-food-buckets-to-feed-the-hamsters

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed string <code>hamsters</code> where <code>hamsters[i]</code> is either:

<ul>
	<li><code>&#39;H&#39;</code> indicating that there is a hamster at index <code>i</code>, or</li>
	<li><code>&#39;.&#39;</code> indicating that index <code>i</code> is empty.</li>
</ul>

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 <code>i</code> can be fed if you place a food bucket at index <code>i - 1</code> and/or at index <code>i + 1</code>.

Return the minimum number of food buckets you should place at empty indices to feed all the hamsters or <code>-1</code> if it is impossible to feed all of them.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/11/01/example1.png" style="width: 482px; height: 162px;" />
<pre>
Input: hamsters = &quot;H..H&quot;
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.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/11/01/example2.png" style="width: 602px; height: 162px;" />
<pre>
Input: hamsters = &quot;.H.H.&quot;
Output: 1
Explanation: We place one food bucket at index 2.
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2022/11/01/example3.png" style="width: 602px; height: 162px;" />
<pre>
Input: hamsters = &quot;.HHH.&quot;
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= hamsters.length &lt;= 105</code></li>
	<li><code>hamsters[i]</code> is either<code>&#39;H&#39;</code> or <code>&#39;.&#39;</code>.</li>
</ul>

minimumBuckets

Minimum Number of Food Buckets to Feed the Hamsters

Maximum Number of People That Can Be Caught in Tag

maximum-number-of-people-that-can-be-caught-in-tag

捉迷藏中可捕获的最大人数

Brightest Position on Street

brightest-position-on-street

街上最亮的位置

Greedy

String

Dynamic Programming

给你一个下标从 0&nbsp;开始的字符串&nbsp;<code>hamsters</code>&nbsp;，其中&nbsp;<code>hamsters[i]</code>&nbsp; 要么是：

<ul>
	<li><code>'H'</code>&nbsp;表示有一个仓鼠在下标&nbsp;<code>i</code>&nbsp;，或者</li>
	<li><code>'.'</code>&nbsp;表示下标&nbsp;<code>i</code>&nbsp;是空的。</li>
</ul>

你将要在空的位置上添加一定数量的食物桶来喂养仓鼠。如果仓鼠的左边或右边至少有一个食物桶，就可以喂食它。更正式地说，如果你在位置&nbsp;<code>i - 1</code>&nbsp;或者 <code>i + 1</code>&nbsp;放置一个食物桶，就可以喂养位置为 <code>i</code>&nbsp;处的仓鼠。

在 空的位置 放置食物桶以喂养所有仓鼠的前提下，请你返回需要的 最少&nbsp;食物桶数。如果无解请返回 <code>-1</code>&nbsp;。

&nbsp;

示例 1：

<img alt="" src="https://pic.leetcode.cn/1710141378-bfEGUX-image.png" style="width: 482px; height: 162px;" />

<pre>
输入：hamsters = "H..H"
输出：2
解释：
我们可以在下标为 1 和 2 处放食物桶。
可以发现如果我们只放置 1 个食物桶，其中一只仓鼠将得不到喂养。
</pre>

示例 2：

<img alt="" src="https://pic.leetcode.cn/1710141384-oLAScv-image.png" style="width: 602px; height: 162px;" />

<pre>
输入：street = ".H.H."
输出：1
解释：
我们可以在下标为 2 处放置一个食物桶。
</pre>

示例 3：

<pre>
输入：street = ".HHH."
输出：-1
解释：
如果我们如图那样在每个空位放置食物桶，下标 2 处的仓鼠将吃不到食物。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= hamsters.length &lt;= 105</code></li>
	<li><code>hamsters[i]</code>&nbsp;要么是&nbsp;<code>'H'</code>&nbsp;，要么是&nbsp;<code>'.'</code> 。</li>
</ul>