Overview

For each cell, check whether there is a guard on the cell itself or on its adjacent cells to the left or right. If there is no guard in any of these positions, that cell is unguarded, so we count it toward the answer.

Analysis

A guard only protects the cell they are standing on and the adjacent cells to their left and right.

Conversely, to determine whether cell \(i\) is guarded, it is sufficient to check at most the following \(3\) cells:

• Cell \(i-1\) to the left
• Cell \(i\) itself
• Cell \(i+1\) to the right

If there is a G among these, cell \(i\) is guarded; otherwise, it is unguarded. However, cells that lie outside the hallway are not checked.

For example, when S = "G...G", the guard at the left end protects the \(1,2\)-th cells from the left, and the guard at the right end protects the \(4,5\)-th cells. Therefore, only the central \(1\) cell is unguarded.

A naive approach that checks all guards for each cell takes \(O(N^2)\) time, which is well within the time limit under these constraints. However, by restricting the check to at most the \(3\) cells mentioned above, we can process it much more efficiently.

Note that simply counting the number of . will not yield the correct answer, because it would also count guarded cells that are adjacent to a guard.

Algorithm

Assume 0-based indexing for the string, from \(0\) to \(N-1\).

1. Initialize the variable ans to \(0\) to store the answer.
2. For each cell \(i\), perform the following:
   1. Initialize a boolean variable guarded to False to indicate whether the cell is guarded.
   2. For each \(j=i-1,i,i+1\), if \(0 \leq j < N\) and S[j] == 'G', set guarded to True.
   3. If guarded is still False, add \(1\) to ans.
3. Output ans.

Since guards that can protect cell \(i\) can only be located at \(i-1,i,i+1\), this check correctly counts all unguarded cells without omission.

Complexity

• Time complexity: \(O(N)\)
  We check at most \(3\) positions for each cell.
• Space complexity: \(O(N)\)
  Required to store the input string. The additional working space excluding the input is \(O(1)\).

Implementation Points

• Before accessing the string, verify that the index is within bounds with 0 <= j < N. In Python especially, S[-1] refers to the last character, so omitting this check can lead to incorrect results when checking the leftmost cell.

• Since a guard also protects their own cell, check S[i] as well, not just the left and right cells.

• Reset guarded to False every time a new cell is inspected.

  Source Code

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    ans = 0
    for i in range(N):
        guarded = False
        for j in (i - 1, i, i + 1):
            if 0 <= j < N and S[j] == 'G':
                guarded = True
        if not guarded:
            ans += 1
    print(ans)

main()

---

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