如何通过颠倒子串来找到词典上最小的字符串？

Question

我有一个字符串S它由a和b's组成。执行一次以下操作。目标是获得词典上最小的字符串。

操作：逆向的S

例如正好一个子

1. 如果S = abab然后Output = aabb（反向串S的ba）
2. 如果S = abba然后Output = aabb（反向串S的bba）

我的做法

案例1：如果所有输入字符串的字符与o相同utput将会是字符串本身。

案例2：如果S的形式aaaaaaa....bbbbbb....，然后回答将是S本身。

否则：查找b在S第一次出现的说，位置是我。字符串S看起来像

aa...bbb...aaaa...bbbb....aaaa....bbbb....aaaaa... 
    | 
    i 

为了获得字典序最小的字符串，将索引i逆转开始的子字符串。请参阅下面的可能结局j。

aa...bbb...aaaa...bbbb....aaaa....bbbb....aaaaa... 
    |   |    |    | 
    i   j    j    j 

反向子S[i:j]对每个j和找到最小的字符串。 该算法的复杂性将是O(|S|*|S|)其中|S|是字符串的长度。

有没有更好的方法来解决这个问题？可能O(|S|)解决方案。

我在想如果我们可以在线性时间内选择正确的j那么我们就完成了。我们会在a的数量最大的情况下选择该j。如果有一个最大值，那么我们解决了这个问题，但如果不是这样的话呢？我尝试了很多。请帮忙。

Answer 1

所以，我想出了一个算法，似乎更有效的O（| S |^2），但我不太确定它的复杂性。这里有一个粗略的概述：

1. 带领的a's，存储在变量start。
2. 将字符串的其余部分分组为字母块。
3. 查找最长序列为a's的组的索引。
4. 如果只剩下一个index，请继续执行10。
5. 筛选这些指数，使得翻转后的[第一]组的b's的长度为最小。
6. 如果只有一个index遗骸，继续进行至10
7. 筛选这些指数，使得[第一]组的a's（不包括前导a's）的逆转后的长度为最小。
8. 如果只有一个index遗骸，继续进行至10
9. 回去5，除了检查[第二/第三/ ...]的a's和b's此时间组。
10. 返回start，再加上扭转团体多达index，加上剩余的群体。

由于正被颠倒任何串开始与b并结束在a，没有两个假设逆转是回文，因此两次反向不会导致相同的输出，以保证有一个独特的最佳解决方案并且该算法将终止。

我的直觉说这种方法可能是O（log（| S |）* | S |），但我不太确定。下面提供了Python中的一个示例实现（尽管不是很好）。

from itertools import groupby 

def get_next_bs(i, groups, off): 
    d = 1 + 2*off 
    before_bs = len(groups[i-d]) if i >= d else 0 
    after_bs = len(groups[i+d]) if i <= d and len(groups) > i + d else 0 
    return before_bs + after_bs 

def get_next_as(i, groups, off): 
    d = 2*(off + 1) 
    return len(groups[d+1]) if i < d else len(groups[i-d]) 

def maximal_reversal(s): 
    # example input: 'aabaababbaababbaabbbaa' 

    first_b = s.find('b') 
    start, rest = s[:first_b], s[first_b:] 
    # 'aa', 'baababbaababbaabbbaa' 

    groups = [''.join(g) for _, g in groupby(rest)] 
    # ['b', 'aa', 'b', 'a', 'bb', 'aa', 'b', 'a', 'bb', 'aa', 'bbb', 'aa'] 

    try: 
     max_length = max(len(g) for g in groups if g[0] == 'a') 
    except ValueError: 
     return s # no a's after the start, no reversal needed 

    indices = [i for i, g in enumerate(groups) if g[0] == 'a' and len(g) == max_length] 
    # [1, 5, 9, 11] 

    off = 0 
    while len(indices) > 1: 
     min_bs = min(get_next_bs(i, groups, off) for i in indices) 
     indices = [i for i in indices if get_next_bs(i, groups, off) == min_bs] 
     # off 0: [1, 5, 9], off 1: [5, 9], off 2: [9] 

     if len(indices) == 1: 
      break 

     max_as = max(get_next_as(i, groups, off) for i in indices) 
     indices = [i for i in indices if get_next_as(i, groups, off) == max_as] 
     # off 0: [1, 5, 9], off 1: [5, 9] 

     off += 1 

    i = indices[0] 
    groups[:i+1] = groups[:i+1][::-1] 

    return start + ''.join(groups) 
    # 'aaaabbabaabbabaabbbbaa' 

Answer 2

TL; DR：这是一种算法，只有在字符串迭代一次（与O（| S |）有限字符串长度-ish复杂性）。

• 遍历字符串，并更新其值解释为反向（LSB到MSB：与我在下面解释实在是有点啰嗦，但算法是很简单的例子）二进制数。
• 如果发现零的序列比当前的最大长度的最后一个零，存储当前的位置，当前反向值。从此，还更新此值，将字符串的其余部分解释为正向（msb-to-lsb）二进制数。
• 如果发现零的序列，只要电流最大，比较与存储的终点的电流值的电流反向值的最后为零;如果它更小，则用当前位置替换终点。

所以你基本上是比较字符串的值，如果它被逆转上涨到目前的点，用字符串的值，如果它只逆转高达（所以远）最佳点，并即时更新这个最佳点。

下面是一个简单的代码示例;它可以毫无疑问地更优雅编码：

function reverseSubsequence(str) { 
 
    var reverse = 0, max = 0, first, last, value, len = 0, unit = 1; 
 
    
 
    for (var pos = 0; pos < str.length; pos++) { 
 
     var digit = str.charCodeAt(pos) - 97;     // read next digit 
 
     if (digit == 0) { 
 
      if (first == undefined) continue;     // skip leading zeros 
 
      if (++len > max || len == max && reverse < value) { // better endpoint found 
 
       max = len; 
 
       last = pos; 
 
       value = reverse; 
 
      } 
 
     } else { 
 
      if (first == undefined) first = pos;    // end of leading zeros 
 
      len = 0; 
 
     } 
 
     reverse += unit * digit;        // update reverse value 
 
     unit <<= 1; 
 
     value = value * 2 + digit;        // update endpoint value 
 
    } 
 
    return {from: first || 0, to: last || 0}; 
 
} 
 
var result = reverseSubsequence("aaabbaabaaabbabaaabaaab"); 
 
document.write(result.from + "&rarr;" + result.to);

（该代码可以通过比较reverse和value被简化每当一个零被发现，而不是只当一最大长的序列的末尾遇到零。）

---

可以创建一个算法，仅遍历输入一次，并且可以处理未知长度的输入流，通过跟踪两个值之一：整个串的解释为反向值（LSB -to-msb）二进制数字，以及一个部分相反的字符串值。只要反向值低于存储的最佳终点的值，就会找到更好的终点。

考虑这个字符串作为一个例子：

aaabbaabaaabbabaaabaaab 

，或者与零和的书面简单：

00011001000110100010001 

我们遍历前导零，直到我们找到的第一个：

0001 
^

这是我们想要扭转序列的开始。我们将开始解释的零和一的流作为逆转（LSB到MSB）二进制数和更新的每一步之后这个数字：

reverse = 1, unit = 1 

然后在每一步中，我们双倍的单位和更新反number：

0001  reverse = 1 
00011  unit = 2; reverse = 1 + 1 * 2 = 3 
000110  unit = 4; reverse = 3 + 0 * 4 = 3 
0001100  unit = 8; reverse = 3 + 0 * 8 = 3 

在这一点上，我们找到一个，并且零序列结束。它包含了2个0，这是目前最大的，所以我们把当前的位置作为一个可能的终点，并且还可以存储当前反向值：

endpoint = {position = 6, value = 3} 

然后我们去遍历字符串，但在每走一步，我们更新了可能的端点的价值，但现在作为一个正常的（MSB到LSB）二进制数：

00011001  unit = 16; reverse = 3 + 1 * 16 = 19 
       endpoint.value *= 2 + 1 = 7 
000110010  unit = 32; reverse = 19 + 0 * 32 = 19 
       endpoint.value *= 2 + 0 = 14 
0001100100 unit = 64; reverse = 19 + 0 * 64 = 19 
       endpoint.value *= 2 + 0 = 28 
00011001000 unit = 128; reverse = 19 + 0 * 128 = 19 
       endpoint.value *= 2 + 0 = 56 

在这一点上，我们发现，我们有3个零的序列，这是比当前最大值2更长，因此我们丢弃迄今为止的终点，并将其替换为当前位置和反向值：

endpoint = {position = 10, value = 19} 

然后我们去遍历字符串：

000110010001   unit = 256; reverse = 19 + 1 * 256 = 275 
        endpoint.value *= 2 + 1 = 39 
0001100100011  unit = 512; reverse = 275 + 1 * 512 = 778 
        endpoint.value *= 2 + 1 = 79 
00011001000110  unit = 1024; reverse = 778 + 0 * 1024 = 778 
        endpoint.value *= 2 + 0 = 158 
000110010001101  unit = 2048; reverse = 778 + 1 * 2048 = 2826 
        endpoint.value *= 2 + 1 = 317 
0001100100011010  unit = 4096; reverse = 2826 + 0 * 4096 = 2826 
        endpoint.value *= 2 + 0 = 634 
00011001000110100 unit = 8192; reverse = 2826 + 0 * 8192 = 2826 
        endpoint.value *= 2 + 0 = 1268 
000110010001101000 unit = 16384; reverse = 2826 + 0 * 16384 = 2826 
        endpoint.value *= 2 + 0 = 2536 

在这里，我们发现，我们有3个零另一个序列，所以我们比较终点的价值当前反向值，发现存储端点具有较低值：

endpoint.value = 2536 < reverse = 2826 

所以我们保持设定的终点定位10，我们去遍历字符串：

0001100100011010001  unit = 32768; reverse = 2826 + 1 * 32768 = 35594 
         endpoint.value *= 2 + 1 = 5073 
00011001000110100010  unit = 65536; reverse = 35594 + 0 * 65536 = 35594 
         endpoint.value *= 2 + 0 = 10146 
000110010001101000100 unit = 131072; reverse = 35594 + 0 * 131072 = 35594 
         endpoint.value *= 2 + 0 = 20292 
0001100100011010001000 unit = 262144; reverse = 35594 + 0 * 262144 = 35594 
         endpoint.value *= 2 + 0 = 40584 

而且我们发现的3个零另一个序列，所以我们比较这个位置的存储终点：

endpoint.value = 40584 > reverse = 35594 

，我们发现它有一个较小的值，所以我们更换可能的终点与当前位置：

endpoint = {position = 21, value = 35594} 

然后我们遍历最后一位：

00011001000110100010001 unit = 524288; reverse = 35594 + 1 * 524288 = 559882 
          endpoint.value *= 2 + 1 = 71189 

因此，在这最后我们发现，21位给我们的最低值，所以它是最佳的解决方案：

00011001000110100010001 -> 00000010001011000100111 
^    ^
start = 3   end = 21 

---

下面是一个使用布尔而不是整数的载体的C++版本。它可以解析超过64个字符的字符串，但复杂性可能是二次的。

#include <vector> 

struct range {unsigned int first; unsigned int last;}; 

range lexiLeastRev(std::string const &str) { 
    unsigned int len = str.length(), first = 0, last = 0, run = 0, max_run = 0; 
    std::vector<bool> forward(0), reverse(0); 
    bool leading_zeros = true; 

    for (unsigned int pos = 0; pos < len; pos++) { 
     bool digit = str[pos] - 'a'; 
     if (!digit) { 
      if (leading_zeros) continue; 
      if (++run > max_run || run == max_run && reverse < forward) { 
       max_run = run; 
       last = pos; 
       forward = reverse; 
      } 
     } 
     else { 
      if (leading_zeros) { 
       leading_zeros = false; 
       first = pos; 
      } 
      run = 0; 
     } 
     forward.push_back(digit); 
     reverse.insert(reverse.begin(), digit); 
    } 
    return range {first, last}; 
}