Welcome to Subscribe On Youtube
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)$.

class Solution { public int minimumChairs(String s) { int cnt = 0, left = 0; for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == 'E') { if (left > 0) { left; } else { ++cnt; } } else { ++left; } } return cnt; } }

class Solution { public: int minimumChairs(string s) { int cnt = 0, left = 0; for (char& c : s) { if (c == 'E') { if (left > 0) { left; } else { ++cnt; } } else { ++left; } } return cnt; } };

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

func minimumChairs(s string) int { cnt, left := 0, 0 for _, c := range s { if c == 'E' { if left > 0 { left } else { cnt++ } } else { left++ } } return cnt }

function minimumChairs(s: string): number { let [cnt, left] = [0, 0]; for (const c of s) { if (c === 'E') { if (left > 0) { left; } else { ++cnt; } } else { ++left; } } return cnt; }