概要

文字列 \(S\) の中で、# が連続する部分の長さの最大値を求めます。各位置から右に # が何個続くかを数え、その最大値を答えとします。

考察

単に文字列全体の # の個数を数えるだけでは正しい答えになりません。. を挟んだ # は連続していないためです。

例えば、S = "##.###." では # は全部で \(5\) 個ありますが、連続する部分の長さは \(2\) と \(3\) なので、答えは \(3\) です。

そこで、各位置を始点として、右方向に # が何個続くかを調べます。. が現れるか、文字列の末尾に達したところで数えるのをやめます。

この方法では同じマスを何度も調べることがありますが、\(N \leq 100\) と小さいため、時間計算量が \(O(N^2)\) の素朴な全探索で十分間に合います。

アルゴリズム

コードでは、文字列の位置を \(0\) から \(N-1\) で表します。

1. 答えを保持する変数 best を \(0\) にします。
2. 各位置 \(i = 0, 1, \ldots, N-1\) について、次の処理を行います。
   • 位置 \(i\) から続く # の個数を表す len を \(0\) にします。
   • \(i+\mathrm{len} < N\) かつ S[i + len] が # である間、len を \(1\) 増やします。
   • best を、現在の best と len の大きい方に更新します。
3. best を出力します。

例えば、S = "##.###." では、各位置から右に続く # の個数は順に \(2, 1, 0, 3, 2, 1, 0\) です。その最大値である \(3\) が答えになります。

最も長い連続部分の左端も必ず始点として調べるため、その部分の長さを漏れなく数えられます。また、数えた範囲はすべて # が連続する部分なので、その最大値が求める答えです。

計算量

• 時間計算量: \(O(N^2)\)
  各始点から最大 \(N\) 文字を調べます。すべての文字が # の場合、調べる文字数は \(N+(N-1)+\cdots+1\) となります。
• 空間計算量: \(O(N)\)
  入力文字列の保存に必要です。文字列以外に使う追加の領域は \(O(1)\) です。

実装のポイント

• s[i + len] を参照する前に、i + len < n を確認します。これにより、文字列の範囲外へのアクセスを防げます。

• len は始点ごとに \(0\) に戻します。

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

• 末尾まで # が続く場合も、範囲チェックによって正しく数え終えられます。

  ソースコード

// 問題文から独立に実装: 各位置から右に何個 '#' が続くかを数えて最大を取る
#include <iostream>
#include <string>
int main() {
    int n; std::string s;
    std::cin >> n >> s;
    int best = 0;
    for (int i = 0; i < n; ++i) {
        int len = 0;
        while (i + len < n && s[i + len] == '#') ++len;
        if (len > best) best = len;
    }
    std::cout << best << std::endl;
}

---

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