解题思路
要让频谱带字典序最小,应尽可能把靠左的字符变成 a。
用双指针配对:
- 左指针 i 从左向右找第一个不是 a 的位置(它可以继续减小)。
- 右指针 j 从右向左找第一个不是 z 的位置(它可以继续增大)。
- 若 i<j,对这一对执行尽可能多次操作:d=min(s[i]−a, z−s[j]),把 s[i] 减小 d、s[j] 增大 d。然后根据是否碰到边界移动指针。
题目内容
一条长度为 n 的频谱带记为字符串 s,仅由小写英文字母构成。每次允许做如下操作任意次:
- 选择两个不同位置 i 和 j(ieqj),要求 s[i]eqa 且 s[j]eqz;
- 将 s[i] 换成字母表中的前一个字母,同时将 s[j] 换成字母表中的后一个字母。
在所有合法操作序列中,取能得到的字典序最小的频谱带。若一次合法操作都不存在,则保持原串。