[舍我其谁-2012]_AC字符串

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个字符串的子串表示原字符串中一段连续的部分。例如,字符串"CBC"的子串总共有六个,它们分别是"C"(前一个),"B","C"(后一个),"CB","BC"和"CBC"。但"CC"不是"CBC"的子串,因为两个'C'在原串中不连续。我们认为空串也不是子串。
现给你一个只含有'A'和'C'两种字符的字符串,问它含有相同'A'和'C'的子串有几个。例如,字符串"ACAC"中符合条件的子串有4个。它们分别是"AC"(前一个),"CA","AC"(后一个),"ACAC"。

Input

单组输入。

输入有两行,首先一个 n,代表接下来输入的字符串长度。

第二行输入为给定的字符串。题目保证字符串长度不超过1000,且只包含 'A' 和 'C' 两种字符。

Output

输出为一个数,表示符合条件的子串的个数。

Sample Input

8
AACCAACC

Sample Output

10

Hint

字符串"AACCAACC"中符合条件的子串分别为"AC"(前一个),"CA","AC"(后一个),"AACC" (前一个),"ACCA","CCAA","CAAC","AACC"(后一个),"ACCAAC","AACCAACC",共10个。
 

Source

【重聚--SDUTACM十周年庆典专场赛】axuhongbo