D - AtCoder Janken 3 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋くんと青木くんが N 回のじゃんけんを行いました。

青木くんが出した手は R, P, S からなる長さ N の文字列 S で表されます。 青木くんが i 回目 (1\leq i\leq N) のじゃんけんに出した手は、S の i 文字目が R のときグー、P のときパー、S のときチョキです。

高橋くんが出した手について、次の条件を満たすことがわかっています。

  • 高橋くんは青木くんに 1 度も負けなかった。
  • i=1,2,\ldots,N-1 について、高橋くんが i 回目のじゃんけんに出した手と i+1 回目のじゃんけんに出した手は異なる。

高橋くんが勝った回数としてありえる最大値を求めてください。

ここで、条件を満たすような高橋くんの手が存在することが証明できます。

制約

  • 1\leq N\leq2\times10 ^ 5
  • S は R, P, S からなる長さ N の文字列
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

6
PRSSRS

出力例 1

5

青木くんは、6 回のじゃんけんでそれぞれパー、グー、チョキ、チョキ、グー、チョキを出しました。

高橋くんは、それぞれチョキ、パー、グー、チョキ、パー、グーを出すことで、1,2,3,5,6 回目のじゃんけんで勝つことができます。

条件を満たす高橋くんの手のうち 6 回のじゃんけんすべてで勝つものは存在しないため、5 を出力してください。

入力例 2

10
SSSSSSSSSS

出力例 2

5

入力例 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

出力例 3

18

Score : 400 points

Problem Statement

Takahashi and Aoki played rock-paper-scissors N times. [Note: In this game, Rock beats Scissors, Scissors beats Paper, and Paper beats Rock.]

Aoki's moves are represented by a string S of length N consisting of the characters R, P, and S. The i-th character of S indicates Aoki's move in the i-th game: R for Rock, P for Paper, and S for Scissors.

Takahashi's moves satisfy the following conditions:

  • Takahashi never lost to Aoki.
  • For i=1,2,\ldots,N-1, Takahashi's move in the i-th game is different from his move in the (i+1)-th game.

Determine the maximum number of games Takahashi could have won.

It is guaranteed that there exists a sequence of moves for Takahashi that satisfies these conditions.

Constraints

  • 1\leq N\leq2\times10 ^ 5
  • S is a string of length N consisting of R, P, and S.
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the maximum number of games Takahashi could have won.

Sample Input 1

6
PRSSRS

Sample Output 1

5

In the six games of rock-paper-scissors, Aoki played Paper, Rock, Scissors, Scissors, Rock, and Scissors.

Takahashi can play Scissors, Paper, Rock, Scissors, Paper, and Rock to win the 1st, 2nd, 3rd, 5th, and 6th games.

There is no sequence of moves for Takahashi that satisfies the conditions and wins all six games, so print 5.

Sample Input 2

10
SSSSSSSSSS

Sample Output 2

5

Sample Input 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

Sample Output 3

18