Balanced Meals

This question is asked by Apple. You are serving people in a lunch line and need to ensure each person gets a "balanced" meal. A balanced meal is a meal where there exists the same number of food items as drink items. Someone is helping you prepare the meals and hands you food items (i.e. F) or a drink items (D) in the order specified by the items string. Return the maximum number of balanced meals you are able to create without being able to modify items.

Note: items will only contain F and D characters.

Example(s)

Example 1:

Input: items = "FDFDFD"
Output: 3
Explanation:
The first "FD" creates the first balanced meal.
The second "FD" creates the second balanced meal.
The third "FD" creates the third balanced meal.
Total: 3 balanced meals

Example 2:

Input: items = "FDFFDFDD"
Output: 2
Explanation:
"FD" creates the first balanced meal (positions 0-1).
"FFDFDD" creates the second balanced meal (positions 2-7).
  This meal has 3 F and 3 D, which is balanced.
Total: 2 balanced meals

Example 3:

Input: items = "FFDD"
Output: 1
Explanation:
"FFDD" creates one balanced meal (2 F and 2 D).
Total: 1 balanced meal

Example 4:

Input: items = "FDFDFDFD"
Output: 4
Explanation:
Each "FD" pair creates a balanced meal.
Total: 4 balanced meals

Solution

The solution uses Greedy Algorithm:

Process items: Go through items left to right
Count F and D: Track count of food and drink items
Greedy matching: When F count equals D count, we have a balanced meal
Reset and continue: After finding a meal, reset counts and continue

JavaScript Solution
Python Solution

JavaScript Solution - Greedy

/**
* Find maximum number of balanced meals
* @param {string} items - String of F and D characters
* @return {number} - Maximum number of balanced meals
*/
function balancedMeals(items) {
let foodCount = 0;
let drinkCount = 0;
let mealCount = 0;

// Process items left to right
for (const item of items) {
  if (item === 'F') {
    foodCount++;
  } else if (item === 'D') {
    drinkCount++;
  }
  
  // When counts are equal, we have a balanced meal
  if (foodCount === drinkCount) {
    mealCount++;
    // Reset counts for next meal
    foodCount = 0;
    drinkCount = 0;
  }
}

return mealCount;
}

// Test cases
console.log('Example 1:', balancedMeals("FDFDFD")); 
// 3

console.log('Example 2:', balancedMeals("FDFFDFDD")); 
// 2

console.log('Example 3:', balancedMeals("FFDD")); 
// 1

console.log('Example 4:', balancedMeals("FDFDFDFD")); 
// 4

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - Greedy

def balanced_meals(items: str) -> int:
  """
  Find maximum number of balanced meals
  
  Args:
      items: String of F and D characters
      
  Returns:
      int: Maximum number of balanced meals
  """
  food_count = 0
  drink_count = 0
  meal_count = 0
  
  # Process items left to right
  for item in items:
      if item == 'F':
          food_count += 1
      elif item == 'D':
          drink_count += 1
      
      # When counts are equal, we have a balanced meal
      if food_count == drink_count:
          meal_count += 1
          # Reset counts for next meal
          food_count = 0
          drink_count = 0
  
  return meal_count

# Test cases
print('Example 1:', balanced_meals("FDFDFD"))  
# 3

print('Example 2:', balanced_meals("FDFFDFDD"))  
# 2

print('Example 3:', balanced_meals("FFDD"))  
# 1

print('Example 4:', balanced_meals("FDFDFDFD"))  
# 4

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Using Stack-like Approach)

Here's an alternative approach using a similar concept:

JavaScript Alternative
Python Alternative

/**
 * Alternative: Track balance (F - D)
 * When balance is 0, we have a balanced meal
 */
function balancedMealsAlternative(items) {
  let balance = 0; // F increases, D decreases
  let mealCount = 0;
  
  for (const item of items) {
    balance += (item === 'F') ? 1 : -1;
    
    // When balance is 0, we have a balanced meal
    if (balance === 0) {
      mealCount++;
    }
  }
  
  return mealCount;
}

def balanced_meals_alternative(items: str) -> int:
    """
    Alternative: Track balance (F - D)
    When balance is 0, we have a balanced meal
    """
    balance = 0  # F increases, D decreases
    meal_count = 0
    
    for item in items:
        balance += 1 if item == 'F' else -1
        
        # When balance is 0, we have a balanced meal
        if balance == 0:
            meal_count += 1
    
    return meal_count

Complexity

Time Complexity: O(n) - Where n is the length of the items string. We iterate through the string once.
Space Complexity: O(1) - Only using a constant amount of extra space.

Approach

The solution uses Greedy Algorithm:

Process items:
- Go through items from left to right
- Cannot modify order, so process sequentially
Count items:
- Track count of F (food) and D (drink) items
- Increment appropriate counter for each item
Greedy matching:
- When foodCount === drinkCount, we have a balanced meal
- Take this meal immediately (greedy choice)
- Reset counts to 0 and continue
Why greedy works:
- If we can form a balanced meal, we should take it immediately
- Any remaining items can form future meals
- This maximizes the number of meals

Key Insights

Greedy algorithm: Take balanced meals as soon as possible
Sequential processing: Must process items in order
Balance tracking: When F count equals D count, we have a meal
O(n) time: Single pass through the string
O(1) space: Only need to track counts

Step-by-Step Example

Let's trace through Example 1: items = "FDFDFD"

items = "FDFDFD"

Process:
  Position 0: 'F'
    foodCount = 1, drinkCount = 0
    Not balanced
  
  Position 1: 'D'
    foodCount = 1, drinkCount = 1
    Balanced! mealCount = 1
    Reset: foodCount = 0, drinkCount = 0
  
  Position 2: 'F'
    foodCount = 1, drinkCount = 0
    Not balanced
  
  Position 3: 'D'
    foodCount = 1, drinkCount = 1
    Balanced! mealCount = 2
    Reset: foodCount = 0, drinkCount = 0
  
  Position 4: 'F'
    foodCount = 1, drinkCount = 0
    Not balanced
  
  Position 5: 'D'
    foodCount = 1, drinkCount = 1
    Balanced! mealCount = 3
    Reset: foodCount = 0, drinkCount = 0

Result: 3 meals

Let's trace through Example 2: items = "FDFFDFDD"

items = "FDFFDFDD"

Process:
  Position 0: 'F'
    foodCount = 1, drinkCount = 0
  
  Position 1: 'D'
    foodCount = 1, drinkCount = 1
    Balanced! mealCount = 1
    Reset: foodCount = 0, drinkCount = 0
  
  Position 2: 'F'
    foodCount = 1, drinkCount = 0
  
  Position 3: 'F'
    foodCount = 2, drinkCount = 0
  
  Position 4: 'D'
    foodCount = 2, drinkCount = 1
  
  Position 5: 'F'
    foodCount = 3, drinkCount = 1
  
  Position 6: 'D'
    foodCount = 3, drinkCount = 2
  
  Position 7: 'D'
    foodCount = 3, drinkCount = 3
    Balanced! mealCount = 2
    Reset: foodCount = 0, drinkCount = 0

Result: 2 meals
  Meal 1: "FD" (positions 0-1)
  Meal 2: "FFDFDD" (positions 2-7)

Visual Representation

Example 1: items = "FDFDFD"

Items:    F  D  F  D  F  D
Position: 0  1  2  3  4  5

Counts:
  F: 1 → 0 → 1 → 0 → 1 → 0
  D: 0 → 1 → 0 → 1 → 0 → 1

Meals:
  Meal 1: positions 0-1 ("FD")
  Meal 2: positions 2-3 ("FD")
  Meal 3: positions 4-5 ("FD")

Result: 3 meals

Example 2: items = "FDFFDFDD"

Items:    F  D  F  F  D  F  D  D
Position: 0  1  2  3  4  5  6  7

Counts:
  F: 1 → 0 → 1 → 2 → 2 → 3 → 3 → 0
  D: 0 → 1 → 0 → 0 → 1 → 1 → 2 → 0

Meals:
  Meal 1: positions 0-1 ("FD")
  Meal 2: positions 2-7 ("FFDFDD")

Result: 2 meals

Edge Cases

Empty string: Return 0 (no meals)
All F: Return 0 (no balanced meals)
All D: Return 0 (no balanced meals)
Single FD: Return 1 (one balanced meal)
Unbalanced end: Remaining items don't form a meal

Important Notes

Cannot modify order: Must process items sequentially
Greedy is optimal: Taking balanced meals immediately maximizes count
Reset after meal: After finding a meal, reset counts
O(n) time: Single pass through string
O(1) space: Only track counts

Why Greedy Works

Key insight:

If we can form a balanced meal, we should take it immediately
Any remaining items can form future meals
Delaying a balanced meal doesn't help (we can't rearrange items)

Proof sketch:

Suppose we have a balanced meal at position i
If we don't take it, we still have the same items available
But we might miss the opportunity if items after i don't balance
Taking it immediately is always safe and optimal

Valid Parentheses: Similar balance tracking
Longest Valid Parentheses: Different balance problem
Partition Labels: Similar greedy approach
Minimum Add to Make Parentheses Valid: Different problem

Takeaways

Greedy algorithm is optimal for this problem
Balance tracking when F count equals D count
O(n) time single pass through string
O(1) space only track counts
Classic greedy problem with practical applications

Example(s)​

Solution​

JavaScript Solution - Greedy

Output:

Python Solution - Greedy

Output:

Alternative Solution (Using Stack-like Approach)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why Greedy Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Using Stack-like Approach)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why Greedy Works

Related Problems

Takeaways