200980: [AtCoder]ARC098 C - Attention

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

Problem Statement

There are $N$ people standing in a row from west to east. Each person is facing east or west. The directions of the people is given as a string $S$ of length $N$. The $i$-th person from the west is facing east if $S_i =$ E, and west if $S_i =$ W.

You will appoint one of the $N$ people as the leader, then command the rest of them to face in the direction of the leader. Here, we do not care which direction the leader is facing.

The people in the row hate to change their directions, so you would like to select the leader so that the number of people who have to change their directions is minimized. Find the minimum number of people who have to change their directions.

Constraints

  • $2 \leq N \leq 3 \times 10^5$
  • $|S| = N$
  • $S_i$ is E or W.

Input

Input is given from Standard Input in the following format:

$N$
$S$

Output

Print the minimum number of people who have to change their directions.


Sample Input 1

5
WEEWW

Sample Output 1

1

Assume that we appoint the third person from the west as the leader. Then, the first person from the west needs to face east and has to turn around. The other people do not need to change their directions, so the number of people who have to change their directions is $1$ in this case. It is not possible to have $0$ people who have to change their directions, so the answer is $1$.


Sample Input 2

12
WEWEWEEEWWWE

Sample Output 2

4

Sample Input 3

8
WWWWWEEE

Sample Output 3

3

Input

题意翻译

给定一个长为 $N$ 的只有 $E$ 或 $W$ 的字符串,选择任意一个点 $a_i$ ,将这个点左边不是 $E$ 的点都变为 $E$,将这个点右边不是 $W$ 的点都变为 $W$,每改一个点付出一点代价。请输出最小的代价。不需要改变 $a_i$ 的方向。 输入有两行,第一行为一个整数 $N$ $(2 ≤ N ≤ 3 × 10^5)$,接下来一行为一个长为 $N$ 的字符串 $S$。 输出一行,输出最小的代价。 对于样例一,指定第三个点,将第一个点改为 $E$ ,代价为一。所以最小的代价为一。

加入题单

上一题 下一题 算法标签: