Overview

We want to find the maximum length of a contiguous segment of # in the string \(S\). We can count how many consecutive #s extend to the right from each position, and the maximum of these counts will be the answer.

Analysis

Simply counting the total number of #s in the entire string does not give the correct answer, because #s separated by . are not contiguous.

For example, in S = "##.###.", there are \(5\) #s in total, but the lengths of the contiguous segments are \(2\) and \(3\), so the answer is \(3\).

Therefore, we check how many #s continue to the right starting from each position. We stop counting when a . appears or when we reach the end of the string.

With this method, the same character may be checked multiple times. However, since \(N \leq 100\) is small, a naive brute-force search with a time complexity of \(O(N^2)\) is well within the time limit.

Algorithm

In the code, string positions (indices) are represented from \(0\) to \(N-1\).

1. Initialize the variable best, which stores the answer, to \(0\).
2. For each position \(i = 0, 1, \ldots, N-1\), perform the following:
   • Initialize len, which represents the number of consecutive #s starting from position \(i\), to \(0\).
   • While \(i+\mathrm{len} < N\) and S[i + len] is #, increment len by \(1\).
   • Update best to the maximum of the current best and len.
3. Output best.

For example, in S = "##.###.", the number of #s continuing to the right from each position is \(2, 1, 0, 3, 2, 1, 0\), respectively. The maximum value, \(3\), is the answer.

Since the leftmost character of the longest contiguous segment is always checked as a starting point, the length of that segment will definitely be counted without omission. Furthermore, because every counted range consists entirely of contiguous #s, the maximum value is indeed the desired answer.

Complexity

• Time complexity: \(O(N^2)\)
  Up to \(N\) characters are inspected from each starting position. If all characters are #, the total number of characters inspected is \(N+(N-1)+\cdots+1\).
• Space complexity: \(O(N)\)
  Required to store the input string. The additional memory used besides the string is \(O(1)\).

Implementation Points

• Check i + len < n before accessing s[i + len]. This prevents out-of-bounds string access.

• Reset len to \(0\) for each starting point.

• By initializing best to \(0\), it will naturally output \(0\) even when there are no #s at all.

• Even when # continues all the way to the end of the string, the bounds check ensures that counting finishes correctly.

  Source Code

// 問題文から独立に実装: 各位置から右に何個 '#' が続くかを数えて最大を取る
#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;
}

This editorial was generated by gpt-6-astra-medium.