计算字符串中将字符分组所需的最小交换次数

Question

我正在尝试解决一个关于字符串的复杂问题：

已知一个仅包含两个不同字符'L'和'R'的长度最多为100000个字符的字符串。序列'RL'被视为“坏的”，需要通过交换来减少这种情况的出现。

然而，该字符串应被视为循环的，因此即使是字符串'LLLRRR'也有一个由最后一个'R'和第一个'L'形成的'RL'序列。

可以进行两个相邻元素的交换。 因此，我们只能交换位置和位置+1上的元素，或者在位置0和n-1（如果字符串的长度（从0开始）是n）之间进行交换。

目标是找到需要进行的最小交换次数，以仅在字符串中留下一个坏连接。

例子：

对于字符串'RLLRRL'，可以通过刚好一次交换来解决问题：交换第一个和最后一个字符（因为字符串是循环的）。 因此，字符串将变为'LLLRRR'，其中有一个坏连接。

我的想法是使用动态规划，计算任何给定'L'所需的交换次数，以将所有其他'L'放在该'L'左侧或右侧。对于任何'R'，我都会计算相同的内容。

此算法在O(N)时间内运行，但它不能给出正确的结果。

当必须交换第一个和最后一个元素时，它无效。我应该添加什么到我的算法中，以使它也适用于这些交换？

- someone12321

---

我无法理解你的逻辑。如果您能提供递归定义，那会很有帮助。 - arunk2

我怀疑你的解决方案是O(N)，因为选择L或R已经是O(N)了，然后你还必须计算每个选定字母的交换次数，这本身听起来就是O(N)，所以你的算法将成为O(N²)。但是没有看到任何代码，无法确定。注：我稍微改写了你的问题，希望更清晰一些，请确认是否可以接受。 - trincot

Answer 1

这个问题可以在线性时间内解决。

一些观察和定义：

• The target of having only one bad connection is another way of saying that the L letters should all be grouped together, as well as the R letters (in a circular string)

• Let a group denote a series of subsequent letters of the same kind that cannot be made larger (because of surrounding letters that differ). By combining individual swaps you can "move" a group with one or more "steps". An example -- I will write . instead of L so it is more easily readable:

  RRR...RR....
  

  There are 4 groups here: RRR, ..., RR and ..... Suppose you want to join the group of two "R" with the left-sided "R" group in the above string. Then you could "move" that middle group with 3 steps to the left by performing 6 swaps:

  RRR...RR....
  RRR..R.R....
  RRR..RR.....
  RRR.R.R.....
  RRR.RR......
  RRRR.R......
  RRRRR.......
  

  These 6 swaps are what constitutes one group move. The cost of the move is 6, and is the product of the size of the group (2) and the distance it travels (3). Note that this move is exactly the same as when we would have moved the group with three "L" characters (cf. the dots) to the right.

  I will use the word "move" in this meaning.

• There is always a solution that can be expressed as a series of group moves, where each group move reduces the number of groups with two, i.e. with each such move, two R groups are merged into one, and consequently also two L groups are merged. In other words, there is always a solution where none of the groups has to split with one part of it moving to the left and another to the right. I will not give a proof of this claim here.

• There is always a solution that has one group that will not move at all: all other groups of the same letter will move towards it. As a consequence there is also a group of the opposite letter that will not move, somewhere at the other end of the circle. Again, I will not prove this here.

• The problem is then equivalent to minimizing the total cost (swaps) of the moves of the groups that represent one of the two letters (so half of all the groups). The other half of the groups move at the same time as was shown in the above example.

算法

一个算法可能是这样的:

创建一个整数数组，其中每个值表示一个组的大小。该数组将按它们出现的顺序列出这些组。这将考虑到循环属性，以便第一组（索引为0）也将考虑到与第一个字母相同的字符串末尾的字母。因此，在偶数索引处，您将拥有表示一个特定字母计数的组，而在奇数索引处，会有另一个字母计数的组。它们表示的两个字母中的哪一个并不重要。组的数组将始终具有偶数个条目。这个数组就是我们解决问题所需要的全部。

选择第一组（索引0），并假设它不会移动。称其为“中间组”。确定哪个是不必移动的相反颜色的组（具有奇数索引）。将这个其他组称为“分裂组”。这个分裂组将把剩余的奇数组分成两部分，它们的值（计数）之和都小于或等于两个总和。这表示对于向一个方向移动的偶数组来说，比向另一个方向移动更便宜，以便与索引0处的组合并。

现在确定将所有偶数组移动到中间组的成本（交换次数）。

这可能是或可能不是一个解决方案，因为选择中间组是任意的。

必须针对任何其他偶数组被选为中间组的情况重复上述过程。

现在算法的精髓是避免在将另一组作为中间组时重新执行整个操作。事实证明，可以将下一个偶数组作为中间组（在索引2处），并在常量时间内调整先前计算出的成本，以得出该中间组的成本。为此，必须记住一些参数：左方向执行移动的成本，右方向执行移动的成本。还需要为每个方向维护偶组大小的总和。最后还需要维护奇组大小的总和，以及两个方向的奇组大小的总和。在将下一个偶数组作为中间组时，可以调整这些参数中的每一个。通常还必须重新识别相应的分裂组，但也可以在平均常量时间内完成。

以下是使用简单JavaScript的工作实现，不再深入讨论：

代码

function minimumSwaps(s) {
    var groups, start, n, i, minCost, halfSpace, splitAt, space,
        cost, costLeft, costRight, distLeft, distRight, itemsLeft, itemsRight;
    // 1. Get group sizes 
    groups = [];
    start = 0;
    for (i = 1; i < s.length; i++) {
        if (s[i] != s[start]) {
            groups.push(i - start);
            start = i;
        }
    }
    // ... exit when the number of groups is already optimal
    if (groups.length <= 2) return 0; // zero swaps
    // ... the number of groups should be even (because of circle)
    if (groups.length % 2 == 1) { // last character not same as first
        groups.push(s.length - start);
    } else { // Ends are connected: add to the length of first group
        groups[0] += s.length - start;
    }
    n = groups.length;
    // 2. Get the parameters of the scenario where group 0 is the middle:
    //    i.e. the members of group 0 do not move in that case.
    // Get sum of odd groups, which we consider as "space", while even 
    // groups are considered items to be moved.
    halfSpace = 0;
    for (i = 1; i < n; i+=2) {
        halfSpace += groups[i];
    }
    halfSpace /= 2;
    // Get split-point between what is "left" from the "middle" 
    // and what is "right" from it:
    space = 0;
    for (i = 1; space < halfSpace; i+=2) {
        space += groups[i];
    }
    splitAt = i-2;
    // Get sum of items, and cost, to the right of group 0
    itemsRight = distRight = costRight = 0;
    for (i = 2; i < splitAt; i+=2) {
        distRight += groups[i-1];
        itemsRight += groups[i];
        costRight += groups[i] * distRight;
    }
    // Get sum of items, and cost, to the left of group 0
    itemsLeft = distLeft = costLeft = 0;
    for (i = n-2; i > splitAt; i-=2) {
        distLeft += groups[i+1];
        itemsLeft += groups[i];
        costLeft += groups[i] * distLeft;
    }
    cost = costLeft + costRight;
    minCost = cost;
    // 3. Translate the cost parameters by incremental changes for 
    //    where the mid-point is set to the next even group
    for (i = 2; i < n; i += 2) {
        distLeft += groups[i-1];
        itemsLeft += groups[i-2];
        costLeft += itemsLeft * groups[i-1];
        costRight -= itemsRight * groups[i-1];
        itemsRight -= groups[i];
        distRight -= groups[i-1];
        // See if we need to change the split point. Items that get 
        // at the different side of the split point represent items
        // that have a shorter route via the other half of the circle.
        while (distLeft >= halfSpace) {
            costLeft -= groups[(splitAt+1)%n] * distLeft;
            distLeft -= groups[(splitAt+2)%n];
            itemsLeft -= groups[(splitAt+1)%n];
            itemsRight += groups[(splitAt+1)%n];
            distRight += groups[splitAt];
            costRight += groups[(splitAt+1)%n] * distRight;
            splitAt = (splitAt+2)%n;
        }
        cost = costLeft + costRight;
        if (cost < minCost) minCost = cost;
    }
    return minCost;
}

function validate(s) {
    return new Set(s).size <= 2; // maximum 2 different letters used
}

// I/O
inp.oninput = function () {
    var s, result, start;
    s = inp.value;
    start = performance.now(); // get timing
    if (validate(s)) {
        result = minimumSwaps(s); // apply algorithm
    } else {
        result = 'Please use only 2 different characters';
    }
    outp.textContent = result;
    ms.textContent = Math.round(performance.now() - start);
}

rnd.onclick = function () {
    inp.value = Array.from(Array(100000), _ => 
                    Math.random() < 0.5 ? "L" : "R").join('');
    if (inp.value.length != 100000) alert('Your browser truncated the input!');
    inp.oninput(); // trigger input handler
}

inp.oninput(); // trigger input handler

input { width: 100% }

<p>
    <b>Enter LR series:</b>
    <input id="inp" value="RLLRRL"><br>
    <button id="rnd">Produce random of size 100000</button>
</p><p>
    <b>Number of swaps: </b><span id="outp"></span><br>
    <b>Time used: </b><span id="ms"></span>ms
</p>

时间复杂度

预处理（创建组数组等）以及计算第一组为中间组时的成本，均由最多n次迭代的非嵌套循环组成，因此这部分是O(n)。

计算中间组为其他偶数组时的成本包括一个循环（用于选择中间组）和另一个内部循环来调整拆分组的选择。即使此内部循环在外部循环的一次迭代中可能迭代多次，总体上此内部循环的迭代次数也不会超过n，因此此外部循环的总执行时间仍然是O(n)。

因此，时间复杂度为O(n)。

请注意，对于100,000个字符的字符串，结果可以在几秒钟内计算出来（参见上面代码段显示的毫秒数）。

- trincot

---

谢谢你的回答和对算法的详细解释，让我意识到如果某些东西看起来很难，其实并不是那么难。 - someone12321

Answer 2

任务是重新排列一个循环列表中的项目，如下所示：

LRLLLRLLLRRLLRLLLRRLRLLLRLLRLRLRLRRLLLRRRLRLLRLLRL  

因此，我们将得到这样的列表：

RRRRRRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRR  

或者这样：

LLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRRLLLLL  

这里有两种类型的项目，它们被分组在一起，但是这两个组的确切位置并不重要。

第一个任务是计算每个组中项目的数量，因此我们需要遍历列表一次。对于上面的示例，结果如下：

#L = 30  
#R = 20  

那么，简单的暴力解决方案是将列表中的每个位置都视为L区域的起点，从位置0开始迭代整个列表，并计算每个项距离它应该在的区域边界有多少步：

LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRR  <- desired output  
LRLLLRLLLRRLLRLLLRRLRLLLRLLRLRLRLRRLLLRRRLRLLRLLRL  <- input  
 <   <   <<  <   >> >   >  > >< <  <<<   > >> >> >  <- direction to move  

我们现在将考虑L区从位置1开始，并重新进行整个计算：

RLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRR  <- desired output  
LRLLLRLLLRRLLRLLLRRLRLLLRLLRLRLRLRRLLLRRRLRLLRLLRL  <- input  
<<   <   <<  <   >> >   >  > >  <  <<<   > >> >> >  <- direction to move  

计算出L区每个位置的总步数后，我们就可以知道哪个位置需要最少的步数。当然，这是一种N²复杂度的方法。

如果我们能够在不再次迭代整个列表的情况下，基于位置X-1处L区的计算，计算出位置X处L区所需的步数，那么这将把复杂度降至N。

为了做到这一点，我们需要跟踪每个区域的两个半部分中错误项的数量，以及每个这四个半区域中错误项的总步数。

LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRR  <- desired output  
<<<<<<<<<<<<<<<>>>>>>>>>>>>>>><<<<<<<<<<>>>>>>>>>>  <- half-zones
LRLLLRLLLRRLLRLLLRRLRLLLRLLRLRLRLRRLLLRRLRRLLRLLRL  <- input  
 <   <   <<  <   >> >   >  > >< <  <<<  >  >> >> >  <- direction to move  
        5              6           5         6      <- wrong items
       43             45          25        31      <- required steps  

当我们向右移动到下一个位置时，左移区域的总步数将减少该区域错误项的数量，右移区域的总步数将增加该区域错误项的数量（因为每个项现在距离该区域的边缘更近/更远，所以需要增加/减少相应的步数）。

        5              6           5         6      <- wrong items
       38             51          20        37      <- required steps  

然而，我们需要检查四个边界点，看看是否有任何错误的项目从一个半区移动到另一个半区，并相应地调整项目和步骤计数。

在这个例子中，原来是 L 区域的第一个项目 L 现在成为了 R 区域的最后一个项目，因此我们将 R> 半区的项目和步骤计数增加到 7 和 38。
另外，原来是 R 区域的第一个项目 L 现在成为了 L 区域的最后一个项目，因此我们将 R< 半区的项目计数减少到 4。
另外，R 区域中间的 L 从 R> 半区移到了 R< 半区，因此我们将 R> 和 R< 的项目计数分别减少和增加到 6 和 5，并将步骤计数减少和增加 10（R> 和 R< 半区的长度）到 28 和 30。

RLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRR  <- desired output  
><<<<<<<<<<<<<<<>>>>>>>>>>>>>>><<<<<<<<<<>>>>>>>>>  <- half-zones
LRLLLRLLLRRLLRLLLRRLRLLLRLLRLRLRLRRLLLRRLRRLLRLLRL  <- input  
><   <   <<  <   >> >   >  > >  <  <<<  <  >> >> >  <- direction to move  
         5              6           5         6     <- wrong items
        38             51          30        28     <- required steps  

当L区从位置0开始时，所需步骤的总数为144。我们已经计算出当L区从位置1开始时，通过查看列表中四个位置发生的情况，而不是必须再次迭代整个列表，总数现在为147。

---

更新

在考虑如何实现此功能时，我意识到，在一个区域中向右移动的错误项数必须与在另一个区域中向左移动的错误项数相同；否则，区域之间的边界就会出现问题。这意味着L和R区域并没有分成两个等长的半区域，并且区域中的“中点”将根据其左侧和右侧的错误项数量而移动。我仍然认为可以将其转化为具有O(N)效率的工作代码，但可能不像我最初描述的那么简单。

- m69 ''snarky and unwelcoming''

---

如果能够在代码中实现并进行测试的话，这将非常有趣。 - trincot

@trincot 我不知道这个星期是否有时间。我认为逻辑是正确的，但会有很多琐碎的细节。 - m69 ''snarky and unwelcoming''

Answer 3

O(n) 时间复杂度解决方案：

L   L   R   L   L   R   R   R   L   L   R   R   L   R
Number of R's to the next group of L's to the left:
1   1       1   1               3   3           2

NumRsToLeft: [1, 1, 3, 2]

Number of swaps needed, where 0 indicates the static L group, and | represents
 the point to the right of which L's move right, wrapping only when not at the end
 (enough L's must move to their right to replace any R's left of the static group):

  2*0       + 2*1          +      2*(3+1)    +    1*(2+3+1)  |
  2*1       + 2*0          +      2*3     |  +    1*(1+1)

There are not enough L's to place the static group in the third or fourth position.

Variables: 0 1 4 6 |
           1 0 3 | 2

Function: 2*v_1 + 2*v_2 + 2*v_3 + 1*v_4

Coefficients (group sizes): [2, 2, 2, 1]

Change in the total swaps needed when moving the static L group from i to (i+1):

 Subtract: PSum(CoefficientsToBeGoingLeft) * NumRsToLeft[i+1]

 Subtract: c_j * PSum(NumRsToLeft[i+1...j]) for c_j <- CoefficientsNoLongerGoingLeft

 Add: (PSum(CoefficientsAlreadyGoingRight) + Coefficients[i]) * NumRsToLeft[i+1]

 Add: c_j * PSum(NumRsToLeft[j+1...i+1]) for c_j <- NewCoefficientsGoingRight

(PSum can be calculated in O(1) time with prefix sums; and the count of coefficients
 converting from a left move to a right move throughout the whole calculation is not
 more than n. This outline does not include the potential splitting of the last new
 group converting from left move to right move.)

- גלעד ברקן