Minimum Number of Food Buckets to Feed the Hamsters - 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. 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 i can be fed if you place a food bucket at index i - 1 and/or at index i + 1.

Return the minimum number of food buckets you should place at empty indices to feed all the hamsters or -1 if it is impossible to feed all of them.

Input & Output

Example 1 — Basic Valid Case

$ Input: hamsters = "H..H.."

› Output: 2

💡 Note: Place buckets at positions 1 and 4. H at position 0 is fed by bucket at 1, H at position 3 is fed by bucket at 4.

Example 2 — Impossible Case

$ Input: hamsters = ".HHH."

› Output: -1

💡 Note: The middle hamster at position 2 cannot be fed because positions 1 and 3 are occupied by other hamsters.

Example 3 — Optimal Sharing

$ Input: hamsters = "H.H"

› Output: 1

💡 Note: Place one bucket at position 1. It feeds both hamsters at positions 0 and 2.

Constraints

1 ≤ hamsters.length ≤ 10⁵
hamsters[i] is either 'H' or '.'

Visualization

Tap to expand

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is that this is a greedy problem where placing buckets as far right as possible maximizes coverage. The optimal approach scans left to right and places buckets greedily. Time: O(n), Space: O(1)

Common Approaches

✓ Brute Force - Try All Combinations

⏱️ Time: O(2ⁿ × n) Space: O(n)

Try every possible combination of placing food buckets at empty positions. For each combination, check if all hamsters are fed and track the minimum number of buckets needed.

Greedy Approach

⏱️ Time: O(n) Space: O(1)

Scan the string left to right. When encountering an unfed hamster, place a bucket at the rightmost valid position (i+1) to potentially feed multiple hamsters efficiently.

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible subsets of empty positions
For each subset, check if all hamsters are fed
Return minimum size among valid subsets

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Empty Spots

Identify all positions where buckets can be placed

Generate Combinations

Try every possible subset of empty positions

Validate Each

Check if current combination feeds all hamsters

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* hamsters) {
    int n = strlen(hamsters);
    
    // Check if impossible (HHH pattern)
    for (int i = 0; i <= n - 3; i++) {
        if (strncmp(&hamsters[i], "HHH", 3) == 0) {
            return -1;
        }
    }
    
    // Find empty positions
    int emptyPositions[1000];
    int emptyCount = 0;
    for (int i = 0; i < n; i++) {
        if (hamsters[i] == '.') {
            emptyPositions[emptyCount++] = i;
        }
    }
    
    if (emptyCount == 0) {
        return strstr(hamsters, "H") != NULL ? -1 : 0;
    }
    
    int minBuckets = INT_MAX;
    
    // Try all possible combinations
    for (int mask = 0; mask < (1 << emptyCount); mask++) {
        int bucketPositions[1000] = {0};
        int bucketCount = 0;
        
        for (int i = 0; i < emptyCount; i++) {
            if (mask & (1 << i)) {
                bucketPositions[emptyPositions[i]] = 1;
                bucketCount++;
            }
        }
        
        // Check if all hamsters are fed
        int allFed = 1;
        for (int i = 0; i < n; i++) {
            if (hamsters[i] == 'H') {
                int fed = 0;
                if (i > 0 && bucketPositions[i - 1]) {
                    fed = 1;
                }
                if (i < n - 1 && bucketPositions[i + 1]) {
                    fed = 1;
                }
                if (!fed) {
                    allFed = 0;
                    break;
                }
            }
        }
        
        if (allFed && bucketCount < minBuckets) {
            minBuckets = bucketCount;
        }
    }
    
    return minBuckets == INT_MAX ? -1 : minBuckets;
}

int main() {
    char hamsters[1001];
    fgets(hamsters, sizeof(hamsters), stdin);
    hamsters[strcspn(hamsters, "\n")] = 0;
    
    int result = solution(hamsters);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2ⁿ possible subsets of empty positions, each taking O(n) to validate

✓ Linear Growth

Space Complexity

O(n)

Space to store current subset and validation arrays

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Minimum Number of Food Buckets to Feed the Hamsters - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler