Minimum Number of Food Buckets to Feed the Hamsters — LeetCode 2086 Python Solution

The problem

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.

Example

Input

hamsters = "H..H"

Output

2

Explanation

We place two food buckets at indices 1 and 2.

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2086. Minimum Number of Food Buckets to Feed the Hamsters is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems