这些 pair 应当形成一个类似括号匹配的结构，但同一个串会有多个可能的匹配，所以直接算匹配会算重。

我们考虑一个贪心匹配的过程：维护一个栈，枚举每个字符，如果它恰好等于栈顶则弹出栈顶，否则压入栈。如果最后栈为空则是完美的。

我们把第一个字符最后被弹出的串称为好串，那么一个完美串可以唯一写成若干个好串的连接。

好串去掉第一个和最后一个字符也是一个完美串，但还要求其中的每个好串的第一个字符和原串的第一个字符不同。

所以我们设长度为 $2n$ 的好串的生成函数是 $G$，则有 $G=cx\frac{1}{1-(c-1)G/c}$，完美串的生成函数为 $F=\frac1{1-G}$。

可以解得 $F=\frac{(2-c)+c\sqrt{1-4(c-1)x}}{2-2c^2x}$，求 $\sqrt{1-4(c-1)x}$ 的前 $n$ 项系数可以在 $O(n)$ 时间内解决，剩余的变换当然也是 $O(n)$ 的。