Overview

We check adjacent characters in the string \(S\) and count the places where the first is a child C and the second is an adult A. In other words, the problem asks us to find the number of occurrences of the contiguous substring CA.

Analysis

The key points are that the child and the adult must be adjacent, and their order must be C → A.

For example, when \(S=\) CCAAC, only the \(2\)-nd character C and the \(3\)-rd character A satisfy the condition, so the answer is \(1\). The \(1\)-st child and the \(3\)-rd adult are not adjacent, so they are not counted.

This problem can be solved sufficiently fast with a naive approach that checks all adjacent pairs in order. Be careful not to count non-adjacent children and adults, or count them in the reverse order AC, as this will lead to a wrong answer.

In the presented code, we focus on the position of the adult and check whether “that person is an adult and the person immediately before them is a child.” This is simply viewing the problem condition from the perspective of the person behind.

Algorithm

Assume \(0\)-based indexing for the string.

1. Initialize the variable cnt to store the answer to \(0\).
2. For \(i=1,2,\ldots,N-1\), check the following conditions:
   • s[i] is A
   • s[i - 1] is C
3. If both are satisfied, increment cnt by \(1\).
4. Finally, output cnt.

This traversal inspects every adjacent pair exactly once. Since it counts only the pairs that form CA, we obtain the desired count.

Complexity

• Time complexity: \(O(N)\) — We inspect the \(N-1\) adjacent pairs.
• Space complexity: \(O(N)\) — Required to store the input string. The additional memory excluding the string is \(O(1)\).

Implementation Notes

• Since s[i - 1] is accessed, the loop starts from i = 1.

• Because the last index of the string is \(N-1\), the loop condition is i < n.

• When \(N=1\), there are no adjacent pairs. The loop is not executed at all, and the correct answer \(0\) is output directly.

  Source Code

// 問題文から独立に実装: 各大人について、その直前が子供かを見る
#include <iostream>
#include <string>
int main() {
    int n; std::string s; std::cin >> n >> s;
    int cnt = 0;
    for (int i = 1; i < n; ++i) if (s[i] == 'A' && s[i - 1] == 'C') cnt++;
    std::cout << cnt << std::endl;
}

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