Minimum Number of Food Buckets to Feed the Hamsters

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

Understanding the Visualization

Input Analysis

String with H (hamsters) and . (empty spots)

Greedy Placement

Place buckets to feed maximum hamsters

Optimal Result

Minimum number of buckets needed

Key Takeaway

🎯 Key Insight: Place food buckets as far right as possible to potentially feed multiple hamsters with each bucket

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

Approach	Time	Space	Notes
✓ Greedy Approach	O(n)	O(1)	Place food buckets optimally by scanning left to right and placing buckets as far right as possible
Brute Force - Try All Combinations	O(2ⁿ × n)	O(n)	Generate all possible food bucket placements and find minimum valid solution

Greedy Approach — Algorithm Steps

Check for impossible patterns (HHH)
Scan left to right for hamsters
For each unfed hamster, place bucket at rightmost valid position
Skip positions that are already covered

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Left to Right

Process each position sequentially

Place Rightmost

For unfed hamsters, place bucket as far right as possible

Skip Fed Areas

Skip positions already covered by placed buckets

Code -

solution.c — C

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

int solution(char* hamsters) {
    int n = strlen(hamsters);
    
    // Check for impossible case: HHH pattern
    for (int i = 0; i <= n - 3; i++) {
        if (strncmp(&hamsters[i], "HHH", 3) == 0) {
            return -1;
        }
    }
    
    int buckets = 0;
    int i = 0;
    
    while (i < n) {
        if (hamsters[i] == 'H') {
            // Check if this hamster is already fed by a bucket to its left
            if (i > 0 && hamsters[i-1] == 'F') {
                i++;
                continue;
            }
            
            // Need to place a bucket to feed this hamster
            // Try to place it as far right as possible
            if (i + 1 < n && hamsters[i + 1] == '.') {
                // Place bucket at i+1
                hamsters[i + 1] = 'F';
                buckets++;
                i += 2;
            } else if (i > 0 && hamsters[i - 1] == '.') {
                // Place bucket at i-1
                hamsters[i - 1] = 'F';
                buckets++;
                i++;
            } else {
                // No valid position to place bucket
                return -1;
            }
        } else {
            i++;
        }
    }
    
    return buckets;
}

int main() {
    char hamsters[100001];
    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(n)

Single pass through the string with constant work per position

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler