string - 计算最小交换次数以对字符串中的字符进行分组

Question

我正在尝试用字符串解决一个非常复杂的问题:

Given 是一个最多包含 100000 个字符的字符串，仅由两个不同的字符“L”和“R”组成。序列“RL”被认为是“坏的”，必须通过应用交换来减少这种发生。

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

可以交换两个连续元素。所以我们只能交换位置 i 和 i+1 上的元素，或者位置 0 和 n-1 上的元素，如果 n 是字符串的长度(字符串是 0 索引的)。

目标是找到在字符串中只留下一个坏连接所需的最少交换次数。

例子

对于字符串 'RLLRRL'，这个问题可以通过一个交换来解决:交换第一个和最后一个字符(因为字符串是循环的)。因此，该字符串将变为 'LLLRRR'，并带有一个错误连接。

我试过的

我的想法是使用动态规划，并计算任何给定的“L”需要多少次交换才能将所有其他“L”放在“L”的左侧，或者放在“L”的右侧。对于任何'R'，我计算相同。

这个算法在 O(N) 时间内工作，但它没有给出正确的结果。

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

Answer 1

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

一些观察和定义:

只有一个坏连接的目标是另一种说法，即 L 字母和 R 字母(在一个圆形字符串中)都应该组合在一起

让一组表示一系列不能变大的相同类型的后续字母(因为周围的字母不同)。通过组合单个交换，您可以通过一个或多个“步骤”“移动”一组。一个例子——我会写 .而不是 L所以它更容易阅读:

RRR...RR....

这里有 4 个群组:RRR , ... , RR和 .... .假设您想将上面字符串中的两个“R”组与左侧的“R”组连接起来。然后，您可以通过执行 6 次交换，向左“移动”3 个步骤的中间组:

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

这 6 次互换构成了一组移动。移动的成本是 6，它是组的大小 (2) 和它移动的距离 (3) 的乘积。请注意，此移动与我们将带有三个“L”字符(参见点)的组向右移动时的移动完全相同。

我将在这个意义上使用“移动”这个词。

总是有一个解决方案可以表示为一系列组移动，其中每个组移动将组的数量减少为两个，即每次这样的移动，两个 R 组合并为一个，因此也合并两个 L 组.换句话说，总有一种解决方案，其中任何组都不必拆分，其中一部分向左移动，另一部分向右移动。我不会在这里提供这种说法的证据。

总是有一个解决方案，其中一组根本不会移动:同一字母的所有其他组都将向它移动。因此，在圆的另一端某处，还有一组相反的字母不会移动。同样，我不会在这里证明这一点。

然后，该问题等效于最小化代表两个字母之一(所有组的一半)的组移动的总成本(交换)。另一半组同时移动，如上例所示。

算法

一个算法可能是这样的:

创建一个整数数组，其中每个值代表一个组的大小。该数组将按组出现的顺序列出组。这将考虑循环属性，因此第一组(索引为 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 个字符的字符串的结果是在几分之一秒内计算出来的(请参阅上述代码段显示的毫秒数)。