石头剪刀布 3 - 代码源竞赛平台

题目描述

蜗蜗和朋友进行了 $N$ 轮石头剪刀布。朋友在第 $i$ 轮出的手势由字符串 $S$ 的第 $i$ 个字符表示：R 是石头，P 是布，S 是剪刀。石头胜剪刀，剪刀胜布，布胜石头；相同手势算平局。

蜗蜗每轮也要出一种手势，且满足两个条件：他不能输掉任何一轮；相邻两轮不能使用相同的手势。已知朋友的全部出手，求蜗蜗最多能赢多少轮。保证存在满足条件的出手方式。

输入格式

第一行包含一个整数 $N$，表示对局轮数。

第二行包含一个长度为 $N$ 的字符串 $S$，表示朋友每轮的手势。

输出格式

输出一行一个整数，表示蜗蜗最多能赢的轮数。

样例

1
R

1

5
RPSRP

5

样例解释

样例 1 中，朋友出石头，蜗蜗出布即可获胜。

样例 2 中，蜗蜗可以依次出布、剪刀、石头、布、剪刀，五轮均获胜，且相邻手势不同。

数据范围

对于 100% 的数据，保证 $1\le N\le 2\times 10^5$；$S$ 的长度为 $N$，且只含 R、P、S。