# Minimum Number of Chairs in a Waiting Room
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-number-of-chairs-in-a-waiting-room)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-chairs-in-a-waiting-room
**Data structures:** String
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia)
---
## Problem
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.

# Approaches
## Brute-Force with Simulation
This approach involves testing every possible number of chairs, from 0 up to the total number of events. For each potential number of chairs, we simulate the entire sequence of events to see if that number is sufficient. The first number of chairs that successfully accommodates everyone is the minimum required.
**Time:** O(N^2), where N is the length of the string `s`. The outer loop runs up to N+1 times, and the inner simulation loop also runs up to N times. · **Space:** O(1), as we only use a few variables to keep track of the state during simulation.
**Pros:** Conceptually simple and easy to understand.; Directly models the problem statement of finding the minimum `k` such that a condition holds.
**Cons:** Inefficient due to nested loops, leading to a quadratic time complexity.; Performs redundant calculations by re-simulating the event sequence for each potential answer.
### Explanation
We can determine the minimum number of chairs by trying out each possible value, let's call it `k`, starting from 0. The maximum possible number of chairs we could ever need is the length of the string `s`, which happens if every event is an entry ('E').

For each `k`, we simulate the process by maintaining a counter for the `currentPeople` in the room. If at any point `currentPeople` exceeds `k`, it means `k` chairs are not enough, so we stop this simulation and try the next value, `k+1`. If we successfully process the entire string `s` without `currentPeople` ever exceeding `k`, it means `k` chairs are sufficient. Since we are checking `k` in increasing order, the first `k` that works is our answer.

```java
class Solution {
    public int minimumChairs(String s) {
        int n = s.length();
        for (int k = 0; k <= n; k++) { // Test if k chairs are sufficient
            int currentPeople = 0;
            boolean possible = true;
            for (char event : s.toCharArray()) {
                if (event == 'E') {
                    currentPeople++;
                } else {
                    currentPeople--;
                }
                if (currentPeople > k) {
                    possible = false;
                    break;
                }
            }
            if (possible) {
                return k; // Found the minimum k
            }
        }
        return n; // Fallback, though a solution should always be found earlier
    }
}
```
### Algorithm
*   Iterate through the number of chairs `k` from 0 to `s.length()`.
*   For each `k`, start a simulation:
    *   Initialize `currentPeople = 0`.
    *   Set a flag `isSufficient = true`.
    *   Iterate through each event `c` in the string `s`.
    *   If `c == 'E'`, increment `currentPeople`.
    *   If `c == 'L'`, decrement `currentPeople`.
    *   If `currentPeople > k` at any point, this `k` is not enough. Set `isSufficient = false` and break the inner loop.
*   If the simulation completes and `isSufficient` is still `true`, then `k` is the minimum number of chairs required. Return `k`.

## Single-Pass Greedy Approach
A much more efficient approach is to simulate the process just once. We can track the number of people currently in the waiting room as we iterate through the events. The minimum number of chairs required is simply the maximum number of people that are in the room at any single point in time.
**Time:** O(N), where N is the length of the string `s`, as we iterate through the string only once. · **Space:** O(1), as we only use a constant number of extra variables regardless of the input size.
**Pros:** Highly efficient with a linear time complexity.; Optimal solution in terms of both time and space.; Simple to implement and understand.
**Cons:** This approach is optimal, so there are no significant drawbacks.
### Explanation
Instead of guessing the number of chairs, we can directly calculate the peak demand. This problem can be solved by finding the maximum number of concurrent people in the waiting room. We can iterate through the event string `s` once, maintaining two variables:

1.  `currentPeople`: The number of people in the waiting room at the current time.
2.  `maxPeople`: The maximum value that `currentPeople` has reached so far.

We initialize both to 0. As we process the string, we update `currentPeople` based on the event ('E' or 'L'). After each update, we check if `currentPeople` has exceeded `maxPeople`. If it has, we update `maxPeople`. The final value of `maxPeople` is the answer.

```java
class Solution {
    public int minimumChairs(String s) {
        int currentPeople = 0;
        int maxPeople = 0;
        for (int i = 0; i < s.length(); i++) {
            char event = s.charAt(i);
            if (event == 'E') {
                currentPeople++;
            } else {
                currentPeople--;
            }
            if (currentPeople > maxPeople) {
                maxPeople = currentPeople;
            }
        }
        return maxPeople;
    }
}
```
### Algorithm
*   Initialize `currentPeople = 0`.
*   Initialize `maxPeople = 0`.
*   Iterate through each character `c` in the string `s`.
*   If `c == 'E'`, increment `currentPeople`.
*   If `c == 'L'`, decrement `currentPeople`.
*   After updating `currentPeople`, update `maxPeople` with the new peak: `maxPeople = Math.max(maxPeople, currentPeople)`.
*   After the loop finishes, return `maxPeople`.

# Solutions
### Python

```python
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

```

### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```