Leetcode 2086: Minimum Number of Buckets Required to Collect Rainwater from Houses

In this problem, we are given a String representing a street with houses and empty spaces. To collect water from the houses, each house must have a bucket placed next to it. We need to return the minimum amount of buckets to do that.

You are given a 0-indexed 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.

Ideas for the solution

The solution is a simple greedy algorithm. Each time we encounter a house at position i, we first check if we already covered it by placing a bucket at position i-1, if not, then we check if the position i+1 is free to place a bucket there. The reason we pick i+1 first and not i-1 is that since we traverse the array in order, putting a bucket in position i+1 could help if there is a house in position i+2, this is the “greedy” part of the algorithm. If there is a house in position i+1, then we check the position i-1. If…