概要

文字列 \(S\) の中で、# が連続している部分の長さの最大値を求めます。左から順に文字を調べ、現在の連続数と、その最大値を管理します。

考察

# の総数を数えるだけでは、途中の . による区切りを考慮できません。例えば ##.### では # は合計 \(5\) 個ありますが、最も長く連続している部分の長さは \(3\) です。

すべての区間を調べる方法も考えられます。この問題の制約は小さいため、そのような方法でも実装によっては十分間に合いますが、区間を列挙する必要はありません。

左から順に見たとき、現在の # の連続数は次のように更新できます。

• # なら、連続数を \(1\) 増やす。
• . なら、連続が途切れるので連続数を \(0\) に戻す。

この連続数の最大値を記録すれば、答えが求まります。

例えば ##.### では、各文字を処理した直後の連続数は \(1, 2, 0, 1, 2, 3\) となり、その最大値 \(3\) が答えです。

アルゴリズム

次の \(2\) つの変数を使います。

• cur：現在見ている文字を末尾とする、連続した # の個数
• ans：これまでに見つかった連続数の最大値

処理手順は以下のとおりです。

1. cur と ans をともに \(0\) で初期化する。
2. 文字列 \(S\) の各文字 c を左から順に調べる。
   • c が # の場合：
     • cur を \(1\) 増やす。
     • cur が ans より大きければ、ans を cur に更新する。
   • c が . の場合：
     • cur を \(0\) にする。
3. ans を出力する。

各連続部分の最後の # を処理した時点で、cur はその部分全体の長さになります。その値を必ず ans に反映するため、すべての文字を調べた後の ans が求める最大値です。

計算量

• 時間計算量: \(O(N)\)。文字列の各文字を \(1\) 回ずつ調べます。
• 空間計算量: \(O(N)\)。入力文字列の保存に必要です。入力の保存を除いた追加の作業領域は、変数のみなので \(O(1)\) です。

実装のポイント

• . に出会ったら、cur を必ず \(0\) に戻します。これを忘れると、離れた # も数えてしまいます。

• # を処理するたびに ans を更新するため、文字列の末尾が # でも特別な処理は不要です。

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

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    s = data[1]
    ans = 0
    cur = 0
    for c in s:
        if c == '#':
            cur += 1
            if cur > ans:
                ans = cur
        else:
            cur = 0
    print(ans)

main()

---

この解説は gpt-6-astra-medium によって生成されました。