概要

文字列 \(S\) を左から順に見ていき、W が何個連続しているかを数えながら、その最大値を記録すれば求められます。
つまり、「現在の連勝数」と「これまでの最大連勝数」を管理するだけの問題です。

考察

この問題で欲しいのは、文字列 \(S\) の中にある W の最長連続部分の長さ です。

例えば

• \(S =\) WWLWWWLW

なら、W の連続部分は

• WW → 長さ \(2\)
• WWW → 長さ \(3\)
• W → 長さ \(1\)

なので答えは \(3\) になります。

重要な気づき

文字列を左から見ていくとき、

• W なら現在の連続数を \(1\) 増やす
• L なら連続が途切れるので \(0\) に戻す

とすれば、その時点での「連続する W の長さ」が分かります。
そして、その値の最大を取り続ければ答えになります。

素朴な方法

各位置から「どこまで W が続くか」を毎回調べる方法も考えられます。
しかしこの方法だと、最悪で各位置ごとにたくさん先まで調べることになり、計算量は \(O(N^2)\) になります。

制約は \(N \le 10^6\) なので、\(O(N^2)\) では間に合いません。

どう解決するか

1 回の走査で済ませればよいです。
「今の連続数」と「最大値」だけを持っておけば、各文字を 1 回ずつ見るだけで答えを求められます。

アルゴリズム

以下の 2 つの変数を用意します。

• cur: 現在連続している W の個数
• ans: これまでの最大連続数

文字列 \(S\) を左から順に見て、

• 文字が W のとき
  cur += 1 とし、ans = max(ans, cur) を行う
• 文字が L のとき
  連続が途切れるので cur = 0 にする

最後に ans を出力すればよいです。

例

\(S =\) WLWWWWLLW

順に見ると：

• W → cur = 1, ans = 1
• L → cur = 0
• W → cur = 1, ans = 1
• W → cur = 2, ans = 2
• W → cur = 3, ans = 3
• W → cur = 4, ans = 4
• L → cur = 0
• L → cur = 0
• W → cur = 1, ans = 4

よって答えは \(4\) です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• L を見たら、現在の連続数 cur を必ず \(0\) に戻します。

• W が 1 つもない場合でも、ans の初期値を \(0\) にしておけばそのまま正しく出力できます。

• \(N\) が大きいので、文字列全体を 1 回だけ見るこの方法が適しています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()

    ans = 0
    cur = 0
    for ch in S:
        if ch == 'W':
            cur += 1
            if cur > ans:
                ans = cur
        else:
            cur = 0

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。