Minimum Number of Chairs in a Waiting Room

Difficulty: Easy | Acceptance: 79.30% | Paid: No Topics: String, Simulation

You are given a string s representing the sequence of people entering and leaving a waiting room. Each character in s is either ‘E’ (enter) or ‘L’ (leave).

When a person enters, they need a chair. When a person leaves, their chair becomes available.

Return the minimum number of chairs needed so that everyone entering has a place to sit.

• Examples
• Constraints
• Simulation Approach
• Prefix Sum Approach

Examples

Example 1:

Input: s = "EEEE"
Output: 4
Explanation: 4 people enter, 0 leave. We need 4 chairs.

Example 2:

Input: s = "ELELE"
Output: 1
Explanation: The sequence is: Enter(1), Leave(0), Enter(1), Leave(0), Enter(1).
The maximum number of people at any time is 1, so we need 1 chair.

Example 3:

Input: s = "ELEELEELLL"
Output: 3
Explanation: The sequence is: Enter(1), Leave(0), Enter(1), Enter(2), Leave(1), 
Enter(2), Enter(3), Leave(2), Leave(1), Leave(0).
The maximum number of people at any time is 3, so we need 3 chairs.

Constraints

1 <= s.length <= 50
s consists only of 'E' and 'L'
It is guaranteed that at any point, the number of people leaving 
will not exceed the number of people who have entered.

Simulation Approach

Intuition Simulate the process by tracking the current number of people in the room and keeping track of the maximum count observed.

Steps

• Initialize a counter for current people and a variable for maximum chairs needed
• Iterate through each character in the string
• Increment counter for ‘E’, decrement for ‘L’
• Update maximum whenever current count exceeds it
• Return the maximum value

class Solution:
    def minimumChairs(self, s: str) -> int:
        current = 0
        max_chairs = 0
        for c in s:
            if c == 'E':
                current += 1
            else:
                current -= 1
            max_chairs = max(max_chairs, current)
        return max_chairs

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) using only constant extra space
• Notes: Most intuitive approach with single pass through the string

Prefix Sum Approach

Intuition Treat ‘E’ as +1 and ‘L’ as -1, then find the maximum prefix sum which represents the peak occupancy.

Steps

• Initialize prefix sum and maximum variables
• For each character, add +1 for ‘E’ or -1 for ‘L’ to running sum
• Track the maximum value of the running sum
• Return the maximum as the answer

class Solution:
    def minimumChairs(self, s: str) -> int:
        prefix_sum = 0
        max_prefix = 0
        for c in s:
            prefix_sum += 1 if c == 'E' else -1
            max_prefix = max(max_prefix, prefix_sum)
        return max_prefix

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) using only constant extra space
• Notes: Mathematically equivalent to simulation but framed as a prefix sum problem