基因

根据字典序贪心，左端点一定是翻转变化后能变小的第一个字符。如果翻转后都不能变小，就翻转最后一个字符，达到最低负面影响。简单讨论知翻转后能变小，要么是本身就是 G 或 T，这样可以单字符变化即变小；要么本身是 C 并且后面有 T，则在C和T之间操作使C变A。这样确定了操作的唯一最优左端点。

对于确定的左端点，枚举所有可能右端点。每次对新的右端点和已知最优右端点进行比较，二分确定两个右端点的各自操作结果中最长公共前缀，比较第一个不同字符，即可比较新答案是否更优。该二分过程中可以通过字符串哈希比较两个操作结果的对应子串是否相同。

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