字符数对

给定一个由字符 o 和 x 组成的长度为 N 的字符串 S。请计算满足以下所有条件的整数对（l，r）的数量：

（1）1≤l≤r≤N；

（2）在字符串 S 的子串 S[l...r]（从第 l 个字符到第 r 个字符）中，同时包含 o 和 x 两种字符。

时间限制：1000ms，内存限制：256MB

输入格式

第一行，一个整数 N；

第二行，一个字符串 S。

输出格式

输出满足条件的整数对的数量。

输入样例#1

4
oxxo

输出样例#1

5

输入样例#2

7
xoxooxx

输出样例#2

19

数据范围：

1≤N≤10⁶；S 仅由字符 o 和 x 组成。

可以通过遍历字符串，统计以每个位置为结尾的，包含字符o和x的子串数量，然后利用数学组合的方式计算满足条件的整数对数量。具体实现如下：

1. 初始化两个变量，一个用于记录字符o出现的次数（记为oCount），另一个用于记录满足条件的子串数量（记为pairCount）。
2. 遍历字符串S，对于每个字符：
   • 如果字符是o，将oCount加1。
   • 如果字符是x且oCount大于0，说明从当前位置到字符串末尾的子串中包含了字符o和x，因此可以将当前位置到字符串末尾的所有子串都作为满足条件的整数对，将区间长度N减去当前位置的值（即r-l）加到pairCount中。
3. 最后输出的pairCount即为满足条件的整数对数量。

本题要求计算满足条件的整数对数量，可以通过遍历字符串并统计相关信息来解决。具体地，我们关心的是字符o和x在字符串中的出现情况。当我们遇到一个字符o时，我们可以将其看作是一个潜在的起点，然后寻找与之匹配的终点x。当我们在某个位置遇到字符x时，如果之前已经有字符o出现过，那么从当前位置到字符串末尾的所有子串都满足条件，因为它们同时包含了o和x两种字符。因此，我们可以将区间长度加到满足条件的整数对数量中。最终输出的结果即为满足条件的整数对数量。

根据题目描述和数据范围，该算法的时间复杂度为O(N)，其中N为字符串的长度。由于题目给定的时间限制为1000ms，该算法可以在规定时间内完成计算。