string - 如何通过反转子字符串找到字典序最小的字符串？

Question

我有一个字符串 S，它由 a 和 b 组成。执行以下操作一次。目标是获取字典序最小的字符串。

操作:恰好反转S

的一个子串

例如

1. if S = abab then Output = aabb(字符串 S 的反转 ba)
2. if S = abba then Output = aabb(字符串 S 的反转 bba)

我的方法

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

情况 2:如果 S 的形式为 aaaaaaa....bbbbbb.... 那么答案将是 S 本身。

otherwise: 在S中找到b的第一次出现，假设位置是i。字符串 S 看起来像

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

为了获得字典序最小的字符串，将要反转的子字符串从索引 i 开始。请参阅下文了解可能的结尾 j。

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

为每个 j 反转子字符串 S[i:j] 并找到最小的字符串。 算法的复杂度将为 O(|S|*|S|)，其中 |S| 是字符串的长度。

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

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

Answer 1

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

1. 领先的地带a's , 存储在变量 start 中.
2. 将字符串的其余部分分组为字母 block 。
3. 找到具有最长序列 a's 的组的索引.
4. 如果只有一个index剩下的，进行10。
5. 过滤这些索引，使 b's 的 [first] 组的长度逆转后最少。
6. 如果只有一个index剩下的，进行10。
7. 过滤这些索引，使 a's 的 [first] 组的长度(不包括领先的 a's )在反转后最少。
8. 如果只有一个index剩下的，进行10。
9. 返回到 5，除了检查 a's 的 [second/third/...] 组和 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'