解法

求めるのは、\(S\) の \(i\) 文字目が C で、\(i+1\) 文字目が A となる \(i\)（\(1 \leq i \leq N - 1\)）の個数です。これは文字列 \(S\) の中で連続する 2 文字が CA になっている箇所の数に他なりません。

そこで、\(i = 1, 2, \ldots, N - 1\) について \(S\) の \(i\) 文字目と \(i+1\) 文字目を順に調べ、C の直後に A が来ている回数を数えればよいです。

正しさの証明

条件を満たす \(i\) は「\(S\) の \(i\) 文字目が C かつ \(i+1\) 文字目が A」と定義されています。アルゴリズムはすべての \(i\)（\(1 \leq i \leq N-1\)）についてこの条件をそのまま検査し、真となるものの個数を数えます。各 \(i\) は独立に判定され、重複して数えたり数え漏らしたりすることはありません。したがって出力される値は条件を満たす \(i\) の個数に正確に一致します。

計算量

• 時間計算量: \(O(N)\)（各位置を 1 回ずつ見る）
• 空間計算量: 入力文字列を保持するために \(O(N)\)、それ以外の補助空間は \(O(1)\)

\(N \leq 100\) なので、これで十分高速です。