2026-10-15重新排列字符串以避免字符对。用go语言现有一个由小写字母组成的字符串 s以及两个互不相同的小写字母 x、y。请把 s 中所有字符重新排序得到另一个字符串 t。要求 t 中每种字符的数量和 s 完全一样并且在 t 里所有 y 都必须出现在所有 x 的前面也就是不能让任何 x 排在某个 y 前面。只要给出一个满足条件的 t 即可。排列的意思是只改变字符顺序不增加也不删除字符。1 s.length 100。s 仅由小写英文字母组成。x 和 y 都是小写英文字母。x ! y。输入 s “aabc”, x “a”, y “c”。输出 “cbaa”。解释字符串 “cbaa” 是 “aabc” 的一个排列且每次出现的 ‘c’ 都在每次出现的 ‘a’ 之前。题目来自力扣3992。大体步骤如下第一步把字符串转换为可修改的字符序列。在 Go 中字符串本身不可直接修改所以代码先执行 t : []byte(s)把字符串 s 转成一个字节切片 t。这个切片中的字符顺序与 s 完全一致后续所有交换都在这个切片上进行。第二步初始化左右两个指针。左指针 l 指向切片的最左端初始为 0右指针 r 指向切片的最右端初始为 len(t)-1。这两个指针表示当前还需要检查和交换的区间是 [l, r]。第三步进入循环条件是 l r。也就是说只要当前区间内至少还有两个字符就继续处理。如果 l 已经不小于 r说明区间内没有两个不同位置的字符需要交换了循环结束。第四步在循环中根据左右指针指向的字符分情况处理。情况一如果左指针位置的字符不是 x。说明这个位置不需要被交换到右边它可能是 y也可能是其他无关字符。于是左指针向右移动一位即 l继续寻找下一个可能是 x 的位置。情况二如果左指针位置是 x但右指针位置的字符不是 y。说明右指针位置不需要被交换到左边它可能是 x也可能是其他无关字符。于是右指针向左移动一位即 r–继续寻找下一个可能是 y 的位置。情况三如果左指针位置是 x同时右指针位置是 y。这时出现了一个逆序对左边是 x右边是 y而题目要求所有 y 必须在所有 x 之前所以这个顺序是错的。于是交换左右指针指向的两个字符。交换后右边的 y 被放到了左边左边的 x 被放到了右边。交换完成后左指针右移一位右指针左移一位因为这两个位置已经处理好了不需要再检查。第五步循环结束返回结果。当 l r 时循环停止。此时所有能够交换的 x 和 y 都已经交换完毕。任何 x 都不再可能出现在 y 的右边因此所有 y 都位于所有 x 的前面。最后把字节切片转回字符串并返回。以题目示例 s “aabc”x ‘a’y ‘c’ 为例具体过程如下初始时t [‘a’, ‘a’, ‘b’, ‘c’]l 0r 3。第一次循环l 0r 3满足 l r。左指针 t[0] ‘a’正好是 x。右指针 t[3] ‘c’正好是 y。于是交换 t[0] 和 t[3]切片变成 [‘c’, ‘a’, ‘b’, ‘a’]。交换后 l 变为 1r 变为 2。第二次循环l 1r 2满足 l r。左指针 t[1] ‘a’是 x。右指针 t[2] ‘b’不是 y。于是右指针左移r 变为 1。此时 l 1r 1不再满足 l r循环结束。返回字符串 “caba”。检查这个结果所有 ‘c’ 都在所有 ‘a’ 之前符合要求。题目给出的输出 “cbaa” 也是一个有效答案两者都满足条件。关于正确性这个算法每次交换都把一个左边的 x 和一个右边的 y 互换位置相当于消除一个“x 在 y 前面”的逆序对。左指针只会向右移动右指针只会向左移动因此每个字符最多被访问一次。当循环结束时左边不可能再有 x 与右边的 y 形成逆序所以所有 y 都在所有 x 之前。关于复杂度总的时间复杂度是 O(n)其中 n 是字符串 s 的长度。因为左指针 l 只从左向右移动右指针 r 只从右向左移动两者合计最多遍历整个字符串一次。循环中的每个分支要么移动 l要么移动 r要么交换后同时移动 l 和 r因此总操作次数与 n 成正比。总的额外空间复杂度是 O(n)。代码中创建了一个与字符串 s 等长的字节切片 t用来存放可修改的字符序列。这个切片需要额外的 O(n) 空间。除此之外只使用了常数个变量如 l、r 等不随 n 增长。因此额外空间复杂度为 O(n)。Go完整代码如下packagemainimport(fmt)funcrearrangeString(sstring,x,ybyte)string{t:[]byte(s)l,r:0,len(t)-1forlr{// 循环直到不足两个字母ift[l]!x{// 寻找最左边的 xl}elseift[r]!y{// 寻找最右边的 yr--}else{t[l],t[r]t[r],t[l]// 交换后[0,l] 都不含 x[r,n-1] 都不含 y问题变成 [l1,r-1] 的子问题lr--}}returnstring(t)}funcmain(){s:aabcx:byte(a)y:byte(c)result:rearrangeString(s,x,y)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defrearrange_string(s:str,x:str,y:str)-str:tlist(s)l,r0,len(t)-1whilelr:ift[l]!x:l1elift[r]!y:r-1else:t[l],t[r]t[r],t[l]l1r-1return.join(t)if__name____main__:saabcxaycresultrearrange_string(s,x,y)print(result)C完整代码如下#includeiostream#includestring#includealgorithmstd::stringrearrangeString(std::string s,charx,chary){intl0;intrstatic_castint(s.size())-1;while(lr){if(s[l]!x){l;}elseif(s[r]!y){--r;}else{std::swap(s[l],s[r]);l;--r;}}returns;}intmain(){std::string saabc;charxa;charyc;std::string resultrearrangeString(s,x,y);std::coutresultstd::endl;return0;}