题解

思路

一个子串能够重排成自己的互补串，当且仅当其中 A 与 T 的数量相同，并且 C 与 G 的数量相同。

做法

给每个字符赋二维增量：A 为 $(1,0)$，T 为 $(-1,0)$，C 为 $(0,1)$，G 为 $(0,-1)$。子串满足条件恰好等价于它的增量和为 $(0,0)$，也就是该子串左右边界对应的二维前缀状态相同。

从空前缀开始扫描，用映射表记录每个前缀状态已经出现的次数。到达当前状态时，它与此前每个相同状态都构成一个合法子串，先把出现次数加入答案，再将该状态的计数加一。

复杂度

时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。