Minimum Number of Chairs in a Waiting Room - Problem

String Simulation Easy

You are given a string s. Simulate events at each second i:

If s[i] == 'E', a person enters the waiting room and takes one of the chairs in it.
If s[i] == 'L', a person leaves the waiting room, freeing up a chair.

Return the minimum number of chairs needed so that a chair is available for every person who enters the waiting room given that it is initially empty.

Input & Output

Example 1 — Basic Mixed Events

$ Input: s = "EELELL"

› Output: 2

💡 Note: Events: Enter, Enter (2 chairs), Leave (1 chair), Enter (2 chairs), Leave, Leave (0 chairs). Maximum chairs needed: 2

Example 2 — Only Entries

$ Input: s = "EEE"

› Output: 3

💡 Note: Three people enter consecutively with no one leaving. Need 3 chairs total.

Example 3 — Alternating Pattern

$ Input: s = "ELEL"

› Output: 1

💡 Note: Enter (1 chair), Leave (0 chairs), Enter (1 chair), Leave (0 chairs). Only 1 chair needed maximum.

Constraints

1 ≤ s.length ≤ 50
s consists only of uppercase English letters 'E' and 'L'
s represents a valid sequence of events

Visualization

Tap to expand

Asked in

a Amazon 15 G Google 12

The key insight is to track the current occupancy and remember the peak. We simulate the events by incrementing a counter for each entry and decrementing for each exit, keeping track of the maximum value seen. Time: O(n), Space: O(1)

Common Approaches

✓ Simulation with Current Count

⏱️ Time: O(n) Space: O(1)

Iterate through each event, increment count for 'E' (enter), decrement for 'L' (leave), and track the maximum count seen.

Single Pass with Counter

⏱️ Time: O(n) Space: O(1)

Use a single counter to track current occupancy. Increment for entries, decrement for exits, and maintain the maximum value seen.

Simulation with Current Count — Algorithm Steps

Initialize current count = 0 and max count = 0
For each character: if 'E' increment current, if 'L' decrement current
Update max count whenever current count increases
Return max count

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with current=0, max=0

Process Events

For each E: increment current, update max. For each L: decrement current

Result

Return the maximum occupancy seen

Code -

solution.c — C

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

int solution(char* s) {
    int currentChairs = 0;
    int maxChairs = 0;
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        if (s[i] == 'E') {
            currentChairs++;
            if (currentChairs > maxChairs) {
                maxChairs = currentChairs;
            }
        } else if (s[i] == 'L') {
            currentChairs--;
        }
    }
    
    return maxChairs;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string of length n

✓ Linear Growth

Space Complexity

O(1)

Only using two integer variables regardless of input size

✓ Linear Space

30.3K Views

Medium Frequency

~8 min Avg. Time

890 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

Minimum Number of Chairs in a Waiting Room - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with Current Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler