You are given a **0-index****ed** string `street`

. Each character in `street`

is either `'H'`

representing a house or `'.'`

representing an empty space.

You can place buckets on the **empty spaces** to collect rainwater that falls from the adjacent houses. The rainwater from a house at index `i`

is collected if a bucket is placed at index `i - 1`

**and/or** index `i + 1`

. A single bucket, if placed adjacent to two houses, can collect the rainwater from **both** houses.

Return *the minimum number of buckets needed so that for every house, there is at least one bucket collecting rainwater from it, or *

`-1`

*if it is impossible.*

**Example 1:**

Input:street = "H..H"Output:2Explanation:We can put buckets at index 1 and index 2. "H..H" -> "HBBH" ('B' denotes where a bucket is placed). The house at index 0 has a bucket to its right, and the house at index 3 has a bucket to its left. Thus, for every house, there is at least one bucket collecting rainwater from it.

**Example 2:**

Input:street = ".H.H."Output:1Explanation:We can put a bucket at index 2. ".H.H." -> ".HBH." ('B' denotes where a bucket is placed). The house at index 1 has a bucket to its right, and the house at index 3 has a bucket to its left. Thus, for every house, there is at least one bucket collecting rainwater from it.

**Example 3:**

Input:street = ".HHH."Output:-1Explanation:There is no empty space to place a bucket to collect the rainwater from the house at index 2. Thus, it is impossible to collect the rainwater from all the houses.

**Example 4:**

Input:street = "H"Output:-1Explanation:There is no empty space to place a bucket. Thus, it is impossible to collect the rainwater from the house.

**Example 5:**

1 2 3 4 5 |
<strong>Input:</strong> street = "." <strong>Output:</strong> 0 <strong>Explanation:</strong> There is no house to collect water from. Thus, 0 buckets are needed. |

**Constraints:**

`1 <= street.length <= 10`

^{5}`street[i]`

is either`'H'`

or`'.'`

.

**Solution: Greedy**

Try to put a bucket after a house if possible, otherwise put it before the house, or impossible.

Time complexity: O(n)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int minimumBuckets(string street) { const int n = street.size(); int ans = 0; for (int i = 0; i < n; ++i) if (street[i] == 'H') if (i - 1 >= 0 and street[i - 1] == 'B') continue; else if (i + 1 < n and street[i + 1] == '.') street[i + 1] = 'B', ++ans; else if (i - 1 >= 0 and street[i - 1] == '.') street[i - 1] = 'B', ++ans; else return -1; return ans; } }; |

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。

如果您喜欢这篇文章／视频，欢迎您捐赠花花。

If you like my articles / videos, donations are welcome.

## Be First to Comment