Overview

We want to find the maximum number of consecutive #s in the string \(S\). By splitting the string by ., we can extract each contiguous segment of #s.

Analysis

Since . represents a cell without a hole, a consecutive sequence of #s is broken there. Therefore, the answer is the maximum length among the substrings obtained by splitting at ..

For example, if \(S\) is ##.###..#, splitting it by . yields:

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

The lengths of these substrings are \(2, 3, 0, 1\), so the answer is \(3\).

Simply counting the total number of #s in the whole string would add up holes in different locations, leading to a Wrong Answer. In the example above, there are \(6\) holes in total, but the longest contiguous segment has a length of \(3\).

Although checking all intervals would pass within the time limit under the current constraints, there is no need to enumerate all intervals. Splitting by . allows us to directly extract the contiguous segments we want to examine.

Algorithm

1. Read \(N\) and \(S\).
2. Split \(S\) at each . using s.split('.').
3. Find the length of each split substring using len(part).
4. Find the maximum of these lengths using max, and output it.

The non-empty substrings after splitting correspond to the contiguous segments of #s separated by .. Furthermore, since all contiguous segments of #s are included in the split result, the maximum length among them is the desired answer.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Splitting the string takes \(O(N)\) time and uses \(O(N)\) space to store the split result. Finding the maximum length across all parts also takes \(O(N)\) time in total.

Implementation Details

• The delimiter is ., not #. Although the initial comment in the provided code might be confusing, the actual operation performed is s.split('.').

• When there are consecutive .s or when . appears at the beginning or end of the string, the split result will contain empty strings "". Since their length is \(0\), they can be handled as-is without any issues.

• If there are no holes, the split result will consist only of empty strings, resulting in a maximum length of \(0\). No special casework is needed.

• If the string consists entirely of #, the string is not split, and the answer will be \(N\).

  Source Code

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

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