AtCoder 猜拳 3

题目描述

高桥君和青木君玩了 $N$ 次石头剪刀布。注：在这个游戏中，石头赢剪刀，剪刀赢布，布赢石头。

青木君的出手由长度为 $N$ 的字符串 $S$ 表示，字符为 R、P、S。$S$ 的第 $i$ 个字符表示青木君第 $i$ 局的出手：R 表示石头，P 表示布，S 表示剪刀。

高桥君的出手满足以下条件：

• 高桥君从未输给青木君。
• 对于 $i=1,2,\ldots,N-1$，高桥君第 $i$ 局的出手与他第 $(i+1)$ 局的出手不同。

求高桥君最多能赢多少局。

题目保证存在满足上述条件的高桥君出手序列。

输入格式

输入按以下格式从标准输入给出。

$N$
$S$

输出格式

输出高桥君最多能赢的局数。

样例

6
PRSSRS

5

在这 $6$ 局石头剪刀布中，青木君依次出了布、石头、剪刀、剪刀、石头、剪刀。

高桥君可以依次出剪刀、布、石头、剪刀、布、石头，从而赢下第 $1$、$2$、$3$、$5$、$6$ 局。

不存在满足条件且能赢下全部 $6$ 局的高桥君出手序列，所以输出 $5$。

10
SSSSSSSSSS

5

24
SPRPSRRRRRPPRPRPSSRSPRSS

18

数据范围

• $1 \le N \le 2 \times 10^5$
• $S$ 是长度为 $N$、由 R、P、S 组成的字符串
• $N$ 是整数