8.1 How many ACs?
(RankList for this Question)
Score: 30pts
Time Limit: 1.00 sec
You are given a string \(s\) of length \(L\) containing alphabets \(A\) and \(C\). You need to print the count of unique subsequences of \(AC\) in string \(s\). Two subsequences are said to be unique if the indices of either character \(A\) or character \(C\) or both differ.<br>

A subsequence is a sequence that can be derived from the given sequence of string by deleting zero or more characters without changing the order of the remaining elements.

Constraints
\(2 \leq L \leq 100000\)
String \(s\) contains only characters ‘A’ and ‘C’.

Input Format
\(L\)
\(s\)

Output Format
An integer, x, denoting the total number of subsequences of \(AC\) in string \(s\).

Example 1
Input:
7
CACCAAC

Output:
5

Explanation:
Explanation -
If we consider the indexing to be done using 0-based indexing, then the index pairs for ‘A’ and ‘C’ are - (1,2), (1,3), (1,6), (4,6), (5,6).

Example 2
Input:
7
ACACACC

Output:
9

Explanation:
The index pairs for ‘A’ and ‘C’ are - (1,2), (1,4), (1,6), (1,7), (3,4), (3,6), (3,7), (5,6), (5,7)

Log In to solve the Question