How to find the lexicographically smallest string by reversing a substring?

Question

I have a string S which consists of a's and b's. Perform the below operation once. Objective is to obtain the lexicographically smallest string.

Operation: Reverse exactly one substring of S

e.g.

1. if S = abab then Output = aabb (reverse ba of string S)
2. if S = abba then Output = aabb (reverse bba of string S)

My approach

Case 1: If all characters of the input string are same then output will be the string itself.

Case 2: if S is of the form aaaaaaa....bbbbbb.... then answer will be S itself.

otherwise: Find the first occurence of b in S say the position is i. String S will look like

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

In order to obtain the lexicographically smallest string the substring that will be reversed starts from index i. See below for possible ending j.

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

Reverse substring S[i:j] for every j and find the smallest string. The complexity of the algorithm will be O(|S|*|S|) where |S| is the length of the string.

Is there a better way to solve this problem? Probably O(|S|) solution.

What I am thinking if we can pick the correct j in linear time then we are done. We will pick that j where number of a's is maximum. If there is one maximum then we solved the problem but what if it's not the case? I have tried a lot. Please help.

Answer 1

So, I came up with an algorithm, that seems to be more efficient that O(|S|^2), but I'm not quite sure of it's complexity. Here's a rough outline:

1. Strip of the leading a's, storing in variable start.
2. Group the rest of the string into letter chunks.
3. Find the indices of the groups with the longest sequences of a's.
4. If only one index remains, proceed to 10.
5. Filter these indices so that the length of the [first] group of b's after reversal is at a minimum.
6. If only one index remains, proceed to 10.
7. Filter these indices so that the length of the [first] group of a's (not including the leading a's) after reversal is at a minimum.
8. If only one index remains, proceed to 10.
9. Go back to 5, except inspect the [second/third/...] groups of a's and b's this time.
10. Return start, plus the reversed groups up to index, plus the remaining groups.

Since any substring that is being reversed begins with a b and ends in an a, no two hypothesized reversals are palindromes and thus two reversals will not result in the same output, guaranteeing that there is a unique optimal solution and that the algorithm will terminate.

My intuition says this approach of probably O(log(|S|)*|S|), but I'm not too sure. An example implementation (not a very good one albeit) in Python is provided below.

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'