3168. Minimum Number of Chairs in a Waiting Room
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.
Example 1:
Input: s = "EEEEEEE"
Output: 7
Explanation:
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
Explanation:
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.
Second | Event | People in the Waiting Room | Available Chairs |
---|---|---|---|
0 | Enter | 1 | 1 |
1 | Leave | 0 | 2 |
2 | Enter | 1 | 1 |
3 | Leave | 0 | 2 |
4 | Enter | 1 | 1 |
5 | Enter | 2 | 0 |
6 | Leave | 1 | 1 |
Example 3:
Input: s = "ELEELEELLL"
Output: 3
Explanation:
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.
Second | Event | People in the Waiting Room | Available Chairs |
---|---|---|---|
0 | Enter | 1 | 2 |
1 | Leave | 0 | 3 |
2 | Enter | 1 | 2 |
3 | Enter | 2 | 1 |
4 | Leave | 1 | 2 |
5 | Enter | 2 | 1 |
6 | Enter | 3 | 0 |
7 | Leave | 2 | 1 |
8 | Leave | 1 | 2 |
9 | Leave | 0 | 3 |
Constraints:
1 <= s.length <= 50
s
consists only of the letters'E'
and'L'
.s
represents a valid sequence of entries and exits.
Solutions
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.
After the traversal, we return cnt
.
The time complexity is $O(n)$, where $n$ is the length of the string s
. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|