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

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

<p>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> <strong>and/or</strong> at index <code>i + 1</code>.</p>

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

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

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

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/11/01/example3.png" style="width: 602px; height: 162px;" />
<pre>
<strong>Input:</strong> hamsters = &quot;.HHH.&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> If we place a food bucket at every empty index as shown, the hamster at index 2 will not be able to eat.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        # length of at most 10^5, and the only two values it can be are 'H' and '.'

        # greedy problem
        # if we place it 
        # hhh.hh # impossible
        # linear sweep placing buckets at empty and checking, but we want to minimize
        # obvious answer is to just place at every . but not optimal answer
        # dp? pick or not pick but if we have to place it then just place it
        # h..h...h, check if period there is adjacent hamster unfedf
        # h.h.hh.h
        # choose the next period that feeds the most hamsters
        # heap that has it's value as (num_hams, index) -> num_hams is the number of unfed hamsters next to it and index is the actual index of the bucket:
        hamsters = ['H'] + list(hamsters) + ['H']
        buckets = 0
        for i in range(1, len(hamsters) - 1):
            if hamsters[i] == 'H':
                if i - 1 >= 0 and hamsters[i-1] == 'B':
                    continue
                if i + 1 < len(hamsters):
                    if hamsters[i+1] == '.':
                        hamsters[i+1] = 'B'
                    else:
                        if i - 1 >= 0:
                            if hamsters[i-1] == 'H':
                                return -1
                            elif hamsters[i-1] == '.':
                                hamsters[i-1] = 'B'
                else: # hamsters is at the end
                    if i - 1 >= 0:
                        if hamsters[i-1] == 'H':
                            return -1
                        elif hamsters[i-1] == '.':
                            hamsters[i-1] = 'B'
        for i in range(len(hamsters)):
            if hamsters[i] == 'B':
                buckets += 1
        return buckets

                

        # go through the array, find unfed hamsters next to each empty, add to max heap
        # take one from max heap, put bucket, feed hamsters, update that these hamsters are fed
        # each time we pop from the heap, check if the hamsters to the left or right are already fed, update number of fed hamsters and check if the next number of unfed hamsters
        heap = []
        num_hamsters = 0
        for i in range(len(hamsters)):
            unfed = 0
            if hamsters[i] == '.':
                if i > 0:
                    unfed += 1 if hamsters[i-1] == 'H' else 0
                if i < len(hamsters) - 1:
                    unfed += 1 if hamsters[i+1] == 'H' else 0

                heap.append((-unfed, i))
            else:
                num_hamsters += 1
        heapq.heapify(heap)
        fed = set()
        buckets = 0
        # print(heap)
        while heap and len(fed) < num_hamsters:
            unfed, index = heapq.heappop(heap)
            unfed *= -1

            if index - 1 in fed:
                unfed -= 1
            if index + 1 in fed:
                unfed -= 1
            if unfed == 0:
                continue
            if heap and -1 * heap[0][0] > unfed:
                heapq.heappush(heap, (-unfed, index))
            else:
                buckets += 1
                if index - 1 >= 0 and hamsters[index-1] == 'H':
                    fed.add(index - 1)
                if index + 1 < len(hamsters) and hamsters[index+1] == 'H':
                    fed.add(index + 1)
        # print(fed)
        if len(fed) == num_hamsters:
            return buckets
        return -1
19700