Overview

We need to find the number of positions where an adult A is immediately behind a child C—that is, how many times the substring "CA" appears in the string \(S\).

Analysis

The condition is satisfied at positions where two adjacent characters form "CA" in this order. For example, if \(S =\) "CACAA", characters \(1,2\) and \(3,4\) from the beginning are "CA", so the answer is \(2\).

Even a naive approach of checking adjacent characters from the beginning takes \(O(N)\) time, which easily runs within the time limit. However, simply counting the total number of children and adults, or pairing children and adults that are not adjacent, cannot verify the “immediately behind” condition.

In this code, we directly count the number of occurrences of "CA" using Python’s count method.

While it is important to note that count counts non-overlapping occurrences, occurrences of "CA" can never overlap with each other. For an overlap to occur, a character would have to simultaneously be the trailing A of one occurrence and the leading C of another, which is impossible. Therefore, s.count("CA") correctly counts all positions that satisfy the condition.

Algorithm

1. Read the number of people \(N\) and the string \(S\).
2. Find the number of occurrences of the substring "CA" using s.count("CA").
3. Output the resulting count.

Any \(2\) adjacent people who satisfy the condition always correspond to "CA", and conversely, any place where "CA" appears always satisfies the condition; hence, this approach yields the correct answer.

Complexity

• Time complexity: \(O(N)\). We search for "CA" of length \(2\) in a string of length \(N\).
• Space complexity: \(O(N)\). Required to store the input string. The auxiliary space excluding the input string is \(O(1)\).

Implementation Notes

• What we count is "CA", not "AC". The string is ordered from the front to the back of the line.

• When \(N = 1\), no \(2\) adjacent people exist. Since count automatically returns \(0\), no special handling is needed.

• Although \(N\) is read as input, it is not used in subsequent calculations because count inspects the entire string.

  Source Code

# 問題文から独立に実装: 部分文字列 "CA" の出現回数（重ならないので count で十分）
n = int(input())
s = input().strip()
print(s.count("CA"))

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