Как найти лексикографически наименьшую строку, перевернув подстроку?

Итак, я придумал алгоритм, который кажется более эффективным, чем 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'

TL;DR: вот алгоритм, который перебирает строку только один раз (с O(|S|)-ой сложностью для строк ограниченной длины). Пример, который я объясню ниже, немного многословен, но алгоритм действительно довольно прост:

• Выполните итерацию по строке и обновите ее значение, интерпретируемое как обратное (от младшего бита к старшему) двоичное число.
• Если вы найдете последний ноль в последовательности нулей, которая длиннее текущего максимума, сохраните текущую позицию и текущее обратное значение. С этого момента также обновите это значение, интерпретируя остальную часть строки как прямое (от старшего к младшему) двоичное число.
• Если вы найдете последний ноль в последовательности нулей, длина которой равна текущему максимуму, сравните текущее обратное значение с текущим значением сохраненной конечной точки; если он меньше, замените конечную точку текущей позицией.

Таким образом, вы в основном сравниваете значение строки, если оно было перевернуто до текущей точки, со значением строки, если оно было перевернуто только до (пока) оптимальной точки, и обновляете эту оптимальную точку на- муха.

Вот пример быстрого кода; его, несомненно, можно было бы закодировать более элегантно:

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 всякий раз, когда встречается ноль, а не только когда встречается конец максимально длинной последовательности нулей.)

Вы можете создать алгоритм, который перебирает ввод только один раз и может обрабатывать входящий поток неизвестной длины, отслеживая два значения: значение всей строки, интерпретируемое как обратное (от младшего бита к старшему) двоичное число, и значение строки с одной перевернутой частью. Всякий раз, когда обратное значение становится ниже значения сохраненной наилучшей конечной точки, лучшая конечная точка была найдена.

Рассмотрим эту строку в качестве примера:

aaabbaabaaabbabaaabaaab

или, записанный с нулями и единицами для простоты:

00011001000110100010001   

Мы перебираем ведущие нули, пока не найдем первый:

0001
   ^

Это начало последовательности, которую мы хотим изменить. Мы начнем интерпретировать поток нулей и единиц как перевернутое (от младшего бита к старшему) двоичное число и будем обновлять это число после каждого шага:

reverse = 1, unit = 1  

Затем на каждом шаге мы удваиваем единицу и обновляем обратное число:

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 нуля, что на данный момент является максимальным, поэтому мы сохраняем текущую позицию как возможную конечную точку, а также сохраняем текущее значение реверса:

endpoint = {position = 6, value = 3} 

Затем мы продолжаем перебирать строку, но на каждом этапе мы обновляем значение возможной конечной точки, но уже как обычное (от старшего до младшего бита) двоичное число:

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++, в которой вместо целых чисел используется вектор bool. Он может анализировать строки длиннее 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};
}