#3168

Easy

LeetCode Problem Workspace

Minimum Number of Chairs in a Waiting Room

Calculate the minimum number of chairs needed in a waiting room using string simulation and event tracking efficiently.

Problem Statement

You are given a string s representing events in a waiting room, where 'E' indicates a person entering and 'L' indicates a person leaving. Simulate each event in sequence and determine the state of the room over time.

Return the minimum number of chairs needed so that each entering person has a seat at every moment, assuming the room starts empty. Ensure that your solution efficiently tracks current occupancy and finds the peak number of simultaneous people.

Examples

Example 1

Input: s = "EEEEEEE"

Output: 7

After each second, a person enters the waiting room and no person leaves it. Therefore, a minimum of 7 chairs is needed.

Example 2

Input: s = "ELELEEL"

Output: 2

Let's consider that there are 2 chairs in the waiting room. The table below shows the state of the waiting room at each second.

Example 3

Input: s = "ELEELEELLL"

Output: 3

Let's consider that there are 3 chairs in the waiting room. The table below shows the state of the waiting room at each second.

Constraints

1 <= s.length <= 50
s consists only of the letters 'E' and 'L'.
s represents a valid sequence of entries and exits.

Solution Approach

Iterate Through Events

Initialize a counter for the current number of people and a variable for the maximum seen. For each character in the string, increase the counter on 'E' and decrease on 'L'. Update the maximum whenever the current count exceeds it.

Track Peak Occupancy

The running maximum of people in the room reflects the peak occupancy. This peak directly translates to the minimum chairs required, avoiding overcounting or undercounting, which is the main failure mode for this problem.

Return Result

After processing all events, the maximum occupancy value is the answer. This approach ensures O(n) time complexity with constant space for counters, perfectly matching the string plus simulation pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is processed once. Space complexity is O(1) as only counters are stored, independent of string length.

What Interviewers Usually Probe

Look for a simple one-pass solution instead of multiple simulations.
Confirm the candidate correctly handles sequences where exits occur before entries.
Check understanding of peak tracking as the critical metric for chair count.

Common Pitfalls or Variants

Common pitfalls

Failing to decrement the counter correctly when processing 'L'.
Using extra data structures unnecessarily, increasing space usage.
Not updating the maximum occupancy at each step, leading to incorrect chair count.

Follow-up variants

Compute minimum chairs if multiple rooms are allowed and people can move between them.
Determine the waiting room occupancy over time as a list instead of just peak value.
Handle cases where the string may contain invalid sequences and raise an error.

FAQ

What is the key insight for the Minimum Number of Chairs in a Waiting Room problem?

The key insight is tracking the running count of people and recording the peak occupancy using a simple string iteration.

Can this problem be solved with additional data structures?

Yes, but using counters is optimal; extra structures like arrays or queues are unnecessary and increase space complexity.

What should I do if an 'L' appears before any 'E'?

Ensure the sequence is valid; the problem guarantees valid sequences, so the counter should not go negative in correct input.

Does the solution pattern relate to other problems?

Yes, it matches the string plus simulation pattern where tracking state changes over time is critical.

How do I know the peak number of people is the correct chair count?

Because the peak occupancy represents the maximum number of people simultaneously present, which equals the minimum chairs needed.

terminal

Solution

Solution 1: Simulation

We use a variable `cnt` to record the current number of chairs needed, and a variable `left` to record the current number of remaining empty chairs. We traverse the string `s`. If the current character is 'E', then if there are remaining empty chairs, we directly use one empty chair, otherwise we need to add a chair; if the current character is 'L', then the number of remaining empty chairs increases by one.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minimumChairs(self, s: str) -> int:
        cnt = left = 0
        for c in s:
            if c == "E":
                if left:
                    left -= 1
                else:
                    cnt += 1
            else:
                left += 1
        return cnt

Continue Practicing

#3174 clear digits #3248 snake in matrix #3271 hash divided string