LeetCode #2086 — MEDIUM

Minimum Number of Food Buckets to Feed the Hamsters

Move from brute-force thinking to an efficient approach using dynamic programming strategy.

The Problem

Problem Statement

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.

Example 1:

Input: hamsters = "H..H"
Output: 2
Explanation: 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.

Example 2:

Input: hamsters = ".H.H."
Output: 1
Explanation: We place one food bucket at index 2.

Example 3:

Input: hamsters = ".HHH."
Output: -1
Explanation: If we place a food bucket at every empty index as shown, the hamster at index 2 will not be able to eat.

Constraints:

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

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Dynamic Programming · Greedy

Example 1

"H..H"

Example 2

".H.H."

Example 3

".HHH."

Core Insight

What unlocks the optimal approach

When is it impossible to feed all the hamsters?
When one or more hamsters do not have an empty space adjacent to it.
Assuming all previous hamsters are fed. If there is a hamster at index i and you are able to place a bucket at index i - 1 or i + 1, where should you put it?
It is always better to place a bucket at index i + 1 because it can feed the next hamster as well.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2086: Minimum Number of Food Buckets to Feed the Hamsters
class Solution {
    public int minimumBuckets(String street) {
        int n = street.length();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (street.charAt(i) == 'H') {
                if (i + 1 < n && street.charAt(i + 1) == '.') {
                    ++ans;
                    i += 2;
                } else if (i > 0 && street.charAt(i - 1) == '.') {
                    ++ans;
                } else {
                    return -1;
                }
            }
        }
        return ans;
    }
}

// Accepted solution for LeetCode #2086: Minimum Number of Food Buckets to Feed the Hamsters
func minimumBuckets(street string) int {
	ans, n := 0, len(street)
	for i := 0; i < n; i++ {
		if street[i] == 'H' {
			if i+1 < n && street[i+1] == '.' {
				ans++
				i += 2
			} else if i > 0 && street[i-1] == '.' {
				ans++
			} else {
				return -1
			}
		}
	}
	return ans
}

# Accepted solution for LeetCode #2086: Minimum Number of Food Buckets to Feed the Hamsters
class Solution:
    def minimumBuckets(self, street: str) -> int:
        ans = 0
        i, n = 0, len(street)
        while i < n:
            if street[i] == 'H':
                if i + 1 < n and street[i + 1] == '.':
                    i += 2
                    ans += 1
                elif i and street[i - 1] == '.':
                    ans += 1
                else:
                    return -1
            i += 1
        return ans

// Accepted solution for LeetCode #2086: Minimum Number of Food Buckets to Feed the Hamsters
/**
 * [2086] Minimum Number of Food Buckets to Feed the Hamsters
 *
 * 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.
 *  
 * Example 1:
 * <img alt="" src="https://assets.leetcode.com/uploads/2022/11/01/example1.png" style="width: 482px; height: 162px;" />
 * Input: hamsters = "H..H"
 * Output: 2
 * Explanation: 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.
 *
 * Example 2:
 * <img alt="" src="https://assets.leetcode.com/uploads/2022/11/01/example2.png" style="width: 602px; height: 162px;" />
 * Input: hamsters = ".H.H."
 * Output: 1
 * Explanation: We place one food bucket at index 2.
 *
 * Example 3:
 * <img alt="" src="https://assets.leetcode.com/uploads/2022/11/01/example3.png" style="width: 602px; height: 162px;" />
 * Input: hamsters = ".HHH."
 * Output: -1
 * Explanation: If we place a food bucket at every empty index as shown, the hamster at index 2 will not be able to eat.
 *
 *  
 * Constraints:
 *
 * 	1 <= hamsters.length <= 10^5
 * 	hamsters[i] is either'H' or '.'.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/minimum-number-of-food-buckets-to-feed-the-hamsters/
// discuss: https://leetcode.com/problems/minimum-number-of-food-buckets-to-feed-the-hamsters/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn minimum_buckets(hamsters: String) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2086_example_1() {
        let hamsters = "H..H".to_string();

        let result = 2;

        assert_eq!(Solution::minimum_buckets(hamsters), result);
    }

    #[test]
    #[ignore]
    fn test_2086_example_2() {
        let hamsters = ".H.H.".to_string();

        let result = 1;

        assert_eq!(Solution::minimum_buckets(hamsters), result);
    }

    #[test]
    #[ignore]
    fn test_2086_example_3() {
        let hamsters = ".HHH.".to_string();

        let result = -1;

        assert_eq!(Solution::minimum_buckets(hamsters), result);
    }
}

// Accepted solution for LeetCode #2086: Minimum Number of Food Buckets to Feed the Hamsters
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #2086: Minimum Number of Food Buckets to Feed the Hamsters
// class Solution {
//     public int minimumBuckets(String street) {
//         int n = street.length();
//         int ans = 0;
//         for (int i = 0; i < n; ++i) {
//             if (street.charAt(i) == 'H') {
//                 if (i + 1 < n && street.charAt(i + 1) == '.') {
//                     ++ans;
//                     i += 2;
//                 } else if (i > 0 && street.charAt(i - 1) == '.') {
//                     ++ans;
//                 } else {
//                     return -1;
//                 }
//             }
//         }
//         return ans;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n × m)

Space

O(n × m)

Approach Breakdown

RECURSIVE

O(2ⁿ) time

O(n) space

Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.

DYNAMIC PROGRAMMING

O(n × m) time

O(n × m) space

Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.

Shortcut: Count your DP state dimensions → that’s your time. Can you drop one? That’s your space optimization.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.