从排列字符串构造原串的最少回跳次数算法问题求解

DevOps 小满

2026-8-8

问题：最小化回跳次数的字符串构造算法设计

问题定义

给定两个长度均为k的字符串$s_1=a_1,a_2,…,a_k$和$s_2=b_1,…,b_k$，其中$s_2$是$s_1$的排列（允许字符重复）。我们需要严格按照$s_1$的字符顺序，从$s_2$中依次选取对应字符并移除，最终构造出$s_1$。

定义回跳次数l：若选取$s_1$中第i个字符对应的$s_2$索引为$idx_i$，选取第i+1个字符对应的索引为$idx_{i+1}$，当$idx_i > idx_{i+1}$时，回跳次数l加1。我们的目标是找到一种字符选取方式，使得l的值最小。

举个例子：当$s_1=abac$、$s_2=acab$时，最优解是1次回跳。具体选择方式为：先选$s_2$中第二个'a'（索引1），再选'b'（索引3），接着回跳选第一个'a'（索引0），最后选'c'（索引2），全程仅1次回跳。

当前指数时间算法分析

你提供了一个朴素递归算法，思路是穷举所有可能的字符选择路径，计算每种路径的回跳次数后取最小值。

算法代码

def solvenaive(s1, s2, curr_ind):
    # 递归终止：s1处理完毕，无回跳次数
    if len(s1) == 0:
        return 0
    first_s1 = s1[0]
    
    # 找到s2中所有与s1首字符匹配的位置
    vorkommen = findOccurrences(s2, first_s1)
    results = []

    # 遍历每个可选位置，递归计算后续最小回跳次数
    for i in vorkommen:
        new_s1 = s1[1:]
        new_s2 = stringPop(s2, i)
        res = solvenaive(new_s1, new_s2, i)
        
        # 若当前选择的位置比上一次小，说明发生回跳，次数加1
        if curr_ind > i:
            results.append(res + 1)
        else:
            results.append(res)
    
    # 返回所有路径中的最小回跳次数
    return min(results)

正确性验证

这个递归算法的逻辑是正确的：

它穷举了每一步所有可选的字符位置，通过递归探索所有可能的构造路径
每次选择时会判断是否触发回跳，并累加对应次数
最终取所有路径中的最小值，符合问题的最优子结构特性

但该算法的时间复杂度是指数级的——当字符串较长且重复字符较多时，可选路径数量会爆炸式增长，无法处理大规模输入。

多项式时间算法设计

这个问题并非NP难问题，可以转化为经典的序列优化问题，得到时间复杂度为O(k log k)的多项式解法，核心思路如下：

问题转化

我们的目标是为$s_1$中的每个字符分配$s_2$中一个未被使用的同字符索引，构造出索引序列$idx_1, idx_2, ..., idx_k$，使得序列中$idx_i > idx_{i+1}$的次数（即回跳次数）最少。

注意到：回跳次数l等于索引序列的连续非递减段数量减1（每个非递减段对应一段无回跳的连续选择，段与段之间需要一次回跳）。因此，最小化l等价于最小化连续非递减段的数量。

具体实现步骤

预处理索引映射：
- 遍历$s_2$，为每个字符c维护一个升序排列的索引列表pos[c]，记录该字符在$s_2$中的所有出现位置。例如$s_2=acab$，则pos['a']=[0,1]，pos['c']=[2]，pos['b']=[3]。
- 为每个pos[c]维护一个指针ptr[c]，初始为0，指向当前可用的最小索引。
贪心+二分维护段末尾：
- 初始化空数组tails，用于存储每个非递减段的最后一个索引。
- 遍历$s_1$中的每个字符c：
  a. 从pos[c]中取出当前可用的最大索引（即pos[c][len(pos[c])-1 - ptr[c]]），然后将ptr[c]加1（标记该索引已被使用）。
  b. 在tails中进行二分查找，找到第一个小于当前索引的位置，将该位置的元素替换为当前索引。这一步的目的是尽可能延长已有的非递减段，避免新增段。
  c. 如果tails中所有元素都大于等于当前索引，说明需要新增一个非递减段，将当前索引加入tails末尾。
- 最终，回跳次数l等于len(tails) - 1。

举个例子，用上述算法处理$s_1=abac$、$s_2=acab$：

处理第一个字符'a'：取可用最大索引1，tails变为[1]，ptr['a']=1
处理第二个字符'b'：取索引3，在tails中找到第一个小于3的位置（0），替换为3，tails变为[3]，ptr['b']=1
处理第三个字符'a'：取可用最大索引0，tails中所有元素（3）都大于0，新增段，tails变为[3,0]，ptr['a']=2
处理第四个字符'c'：取索引2，在tails中找到第一个小于2的位置（1，对应元素0），替换为2，tails变为[3,2]
最终len(tails)=2，回跳次数l=2-1=1，与最优解一致。

结论

这个问题可以通过多项式时间算法解决，无需暴力穷举。上述贪心+二分的方法时间复杂度为O(k log k)，能够高效处理大规模输入。

内容的提问来源于stack exchange，提问作者NiceGuySaysHi

从排列字符串构造原串的最少回跳次数算法问题求解

问题定义 #

当前指数时间算法分析 #

算法代码 #

正确性验证 #

多项式时间算法设计 #

问题转化 #

具体实现步骤 #

结论 #