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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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.

Solution

Method 1 – Simulation with Counter

Intuition

We simulate the process by tracking the number of people in the room at each event. The maximum number of people present at any time is the minimum number of chairs needed.

Approach

  1. Initialize a counter for current people and a variable for the maximum.
  2. Iterate through the string:
    • If ‘E’, increment the counter.
    • If ‘L’, decrement the counter.
    • Update the maximum after each event.
  3. Return the maximum value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int minimumChairs(string s) {
        int curr = 0, ans = 0;
        for (char c : s) {
            if (c == 'E') curr++;
            else curr--;
            ans = max(ans, curr);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func minimumChairs(s string) int {
    curr, ans := 0, 0
    for _, c := range s {
        if c == 'E' {
            curr++
        } else {
            curr--
        }
        if curr > ans {
            ans = curr
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int minimumChairs(String s) {
        int curr = 0, ans = 0;
        for (char c : s.toCharArray()) {
            if (c == 'E') curr++;
            else curr--;
            ans = Math.max(ans, curr);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minimumChairs(s: String): Int {
        var curr = 0
        var ans = 0
        for (c in s) {
            if (c == 'E') curr++ else curr--
            ans = maxOf(ans, curr)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def minimumChairs(self, s: str) -> int:
        curr: int = 0
        ans: int = 0
        for c in s:
            if c == 'E':
                curr += 1
            else:
                curr -= 1
            ans = max(ans, curr)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn minimum_chairs(s: String) -> i32 {
        let mut curr = 0;
        let mut ans = 0;
        for c in s.chars() {
            if c == 'E' {
                curr += 1;
            } else {
                curr -= 1;
            }
            ans = ans.max(curr);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    minimumChairs(s: string): number {
        let curr = 0, ans = 0;
        for (const c of s) {
            if (c === 'E') curr++;
            else curr--;
            ans = Math.max(ans, curr);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(1), only a few variables are used.