Minimum Number of Chairs in a Waiting Room

Problem Description

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.

Key Insights

• A person can enter the waiting room ('E') or leave it ('L').
• We need to track the number of people currently in the waiting room and the number of chairs available.
• The maximum number of people in the waiting room at any time gives the minimum number of chairs required.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we will use a simple simulation approach. We will iterate through each character in the string:

• If the character is 'E', we increment the count of people currently in the waiting room.
• If the character is 'L', we decrement the count of people.
• Throughout the iteration, we maintain a variable to track the maximum number of people in the waiting room at any time, which represents the minimum number of chairs needed.

Code Solutions