概要

文字列 \(S\) に含まれる、連続した # の個数の最大値を求めます。. で文字列を分割すると、それぞれの # の連続部分を取り出せます。

考察

. は穴のないマスなので、# の連続はそこで途切れます。したがって、. を区切りとして分割した各文字列の長さの最大値が答えです。

例えば、\(S\) が ##.###..# の場合、. で分割すると次のようになります。

["##", "###", "", "#"]

それぞれの長さは \(2, 3, 0, 1\) なので、答えは \(3\) です。

単に文字列全体に含まれる # の個数を数えるだけでは、離れた場所の穴も合計してしまい、誤答になります。上の例では穴は全部で \(6\) 個ありますが、最長の連続部分は \(3\) 個です。

すべての区間を調べる方法でも今回の制約では間に合いますが、区間を列挙する必要はありません。. で分割すれば、調べたい連続部分を直接取り出せます。

アルゴリズム

1. \(N\) と \(S\) を読み込みます。
2. s.split('.') で、\(S\) を . ごとに分割します。
3. 分割した各文字列の長さを len(part) で求めます。
4. その最大値を max で求め、出力します。

分割後の空でない文字列は、. によって区切られた # の連続部分と一致します。また、すべての # の連続部分が分割結果に含まれるため、その長さの最大値が求める答えになります。

計算量

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

文字列の分割には \(O(N)\) 時間かかり、分割結果を保存するために \(O(N)\) の空間を使います。各部分の長さの最大値を求める処理も、全体で \(O(N)\) 時間です。

実装のポイント

• 区切り文字は # ではなく . です。提示コードの先頭コメントは紛らわしいですが、実際の処理は s.split('.') となっています。

• . が連続する場合や、先頭・末尾にある場合は、分割結果に空文字列 "" が含まれます。その長さは \(0\) なので、そのまま扱って問題ありません。

• 穴がない場合も、分割結果は空文字列だけになり、最大の長さとして \(0\) が得られます。特別な場合分けは不要です。

• すべてが # の場合は文字列が分割されず、答えは \(N\) になります。

  ソースコード

# 問題文から独立に実装: '#' で区切られた連続区間の最大長
n = int(input())
s = input().strip()
print(max(len(part) for part in s.split('.')))

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