Overview

We inspect every pair of adjacent characters in the string \(S\) and count the number of occurrences of CA.

Analysis

A child is represented by C, and an adult is represented by A. Therefore, the condition “an adult is directly behind a child” is equivalent to having an A immediately after a C in the string.

For example, when \(S =\) CCAAC, the pairs of adjacent characters from front to back are as follows:

• CC: does not satisfy the condition
• CA: satisfies the condition
• AA: does not satisfy the condition
• AC: does not satisfy the condition

Therefore, the answer is \(1\).

For this problem, a naive approach of checking all adjacent characters is fast enough to solve it. There is no need to check all combinations of adults and children.

Also, if you count all adults who are behind a child, you will end up including people who do not satisfy the “directly behind” condition. Be sure to check only adjacent positions.

Algorithm

1. Initialize the answer variable ans to \(0\).
2. Using \(0\)-based indexing, iterate through \(i = 0, 1, \ldots, N-2\).
3. If s[i] is C and s[i + 1] is A, add \(1\) to ans.
4. Output ans.

Every valid occurrence corresponds to two adjacent characters. Since this method checks each of them exactly once, the correct count is obtained.

Complexity

• Time complexity: \(O(N)\)
  We check each of the \(N-1\) adjacent pairs once.
• Space complexity: \(O(N)\)
  Required to store the input string. The additional working space excluding the input is \(O(1)\).

Implementation Notes

• In Python, string indexing is \(0\)-based. To prevent s[i + 1] from going out of bounds, use range(n - 1) for the loop.

• CA and AC are different. Since the child is in front and the adult is behind, the condition is s[i] == 'C' and s[i + 1] == 'A'.

• In the reference solution, a \(1\) is yielded every time the condition is met and summed using sum. Since it uses a generator expression, no temporary list is created for aggregation.

• When \(N=1\), there are no adjacent people. Since range(n - 1) is empty and sum returns \(0\), no special case handling is needed.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    s = data[1]
    ans = sum(1 for i in range(n - 1) if s[i] == 'C' and s[i + 1] == 'A')
    print(ans)

main()

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