如何通过反转子串来找到按字典顺序排列的最小字符串？

Question

我有一个S由a's和b's 组成的字符串.执行以下操作一次.目的是获得按字典顺序排列的最小字符串.

操作: 正好反转一个子串S

例如

1. 如果S = abab那么Output = aabb(ba字符串反向S)
2. 如果S = abba那么Output = aabb(bba字符串反向S)

我的方法

情况1:如果输入字符串的所有字符都相同,则输出将是字符串本身.

案例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在线性时间内选择正确的,那么我们就完成了.我们将选择j的数量a最大的j .如果有一个最大值,那么我们就解决了问题,但是如果不是这样的话呢？我已经尝试了很多.请帮忙.

Answer 1

所以，我想出了一个算法，它似乎比 O(|S|^2) 更有效，但我不太确定它的复杂性。这是一个粗略的轮廓：

1. 前导条带a's，存储在变量中start。
2. 将字符串的其余部分分组为字母块。
3. 找出具有最长序列的组的索引a's。
4. 如果index只剩下 1 个，则继续执行 10。
5. 过滤这些索引，使得反转后的[第一]组的长度b's最小。
6. 如果index只剩下 1 个，则继续执行 10。
7. 过滤这些索引，使反转后的 [first] 组a's（不包括前导a's）的长度最小。
8. 如果index只剩下 1 个，则继续执行 10。
9. 返回到 5，除了这次检查 [第二/第三/...] 组 和a's。b's
10. 返回start，加上直到 的反转组index，再加上剩余的组。

由于任何被反转的子串都以 a 开头b并以 an 结尾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'