or '.'.

Solution

Method 1 – Greedy Placement

Intuition

To minimize buckets, we should place a bucket to the right of each hamster if possible, otherwise to the left. If neither is possible, it's impossible to feed all hamsters.

Approach

Iterate through the string.
For each hamster at index i:
- If the right cell is empty and not already used, place a bucket at i+1.
- Else if the left cell is empty and not already used, place a bucket at i-1.
- Else, return -1 (impossible).
Track bucket placements to avoid double counting.
Return the total number of buckets placed.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minimumBuckets(string hamsters) {\n        int n = hamsters.size(), ans = 0;\n        vector<bool> bucket(n, false);\n        for (int i = 0; i < n; ++i) {\n            if (hamsters[i] == 'H') {\n                if (i+1 < n && hamsters[i+1] == '.' && !bucket[i+1]) {\n                    bucket[i+1] = true;\n                    ans++;\n                } else if (i-1 >= 0 && hamsters[i-1] == '.' && !bucket[i-1]) {\n                    bucket[i-1] = true;\n                    ans++;\n                } else {\n                    return -1;\n                }\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minimumBuckets</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">string</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> hamsters</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> hamsters.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">size</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(), ans </span><span style=\"c

Related Tags