Overview

Find the maximum length of a contiguous segment of #s in the string \(S\). We examine the characters from left to right, keeping track of the current streak length and the maximum streak length seen so far.

Analysis

Simply counting the total number of #s is not sufficient, as it does not account for delimiters (.). For example, in ##.###, there are \(5\) #s in total, but the maximum length of a contiguous segment is \(3\).

One could also consider checking all substrings. Given the small constraints of this problem, such an approach could pass within the time limit depending on the implementation, but enumerating all intervals is unnecessary.

When scanning from left to right, the current consecutive count of #s can be updated as follows:

• If it is #, increase the consecutive count by \(1\).
• If it is ., the streak is broken, so reset the consecutive count to \(0\).

By recording the maximum value of this consecutive count, we can find the answer.

For example, in ##.###, the consecutive count immediately after processing each character is \(1, 2, 0, 1, 2, 3\), and the maximum value \(3\) is the answer.

Algorithm

We use the following \(2\) variables:

• cur: the number of consecutive #s ending at the current character
• ans: the maximum consecutive count found so far

The procedure is as follows:

1. Initialize both cur and ans to \(0\).
2. Iterate through each character c of string \(S\) from left to right.
   • If c is #:
     • Increase cur by \(1\).
     • If cur is greater than ans, update ans with cur.
   • If c is .:
     • Set cur to \(0\).
3. Output ans.

When processing the last # of each contiguous segment, cur becomes the total length of that entire segment. Since this value is guaranteed to be reflected in ans, the value of ans after examining all characters will be the desired maximum.

Complexity

• Time complexity: \(O(N)\). Each character in the string is examined once.
• Space complexity: \(O(N)\). Required to store the input string. Excluding the storage for the input, the auxiliary space is \(O(1)\) since only a few variables are used.

Implementation Notes

• Make sure to reset cur to \(0\) whenever you encounter .. Forgetting this will cause disjoint # segments to be counted together.

• Since ans is updated every time # is processed, no special handling is needed even if the string ends with #.

• By initializing ans to \(0\), the program will correctly output \(0\) even if there are no # characters at all.

  Source Code

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()

---

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