Minimum Number of Food Buckets to Feed the Hamsters

Intuition

• In the worst case, each hamster needs one donut.
• However, in the case of H.H, two hamsters share 1 donut, meaning there is one less donut needed for each H.H case.

Complexity

Runtime

$O(N)$ to do a bunch of string manipulation on a string of size N

Space

$O(N)$ to store the resultant string.

Code

Tcarcus

 if "HHH" in hamsters or hamsters[:2] == "HH" or hamsters[-2:] == "HH" or hamsters == "H":
            return -1
 
        return hamsters.count("H") - hamsters.count("H.H")

Smartcoder

class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        n = len(hamsters)
        if hamsters.count('H') == n or 'HHH' in hamsters or hamsters == 'H' or (n >= 2 and (hamsters[:2] == 'HH' or hamsters[-2:] == 'HH')):
            return -1
        h = list(hamsters)
        ans = 0
        for i in range(1, n-1):
            if h[i-1] + h[i] + h[i+1] == 'H.H':
                h[i-1] = 'X'
                h[i] = 'X'
                h[i+1] = 'X'
                ans += 1
        return ans + h.count('H')

class Solution:
    def minimumBuckets(self, hamsters: str) -> int:
        n = len(hamsters)
        if n == 1:
            if hamsters[0] == 'H':
                return -1
            return 0
        if n == 2:
            if hamsters[0] == hamsters[1] == 'H':
                return -1
            elif hamsters[0] == hamsters[1] == '.':
                return 0
            return 1
 
        hamsters = list(hamsters)
        counter = Counter(hamsters)
        if '.' in counter and counter['.'] == n:
            return 0
 
        # Check for HH on left or right (edge case)
        if hamsters[0] == hamsters[1] == 'H' or hamsters[-1] == hamsters[-2] == 'H':
            return -1
 
        # Check for HHH
        for right in range(2, n):
            if hamsters[right - 2] == hamsters[right - 1] == hamsters[right] == 'H':
                return -1
 
        # Check for H.H
        count = 0
        left = 0
        for right in range(2, n):
            if hamsters[right - 2] == hamsters[right] == 'H':
                hamsters[right - 1] = 'X'
                hamsters[right - 2] = 'X'
                hamsters[right] = 'X'
                count += 1
        return count + hamsters.count('H')

Notes

---

References

Minimum Number of Food Buckets to Feed the Hamsters - LeetCode