Skip to content

Latest commit

 

History

History
323 lines (275 loc) · 6.51 KB

README_EN.md

File metadata and controls

323 lines (275 loc) · 6.51 KB
Raw
comments difficulty edit_url rating source tags
true
Easy
1211
Weekly Contest 400 Q1
String
Simulation

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)$.

Python3

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

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

C++

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

Go

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
}

TypeScript

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