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

Ответ 1

Итак, я придумал алгоритм, который кажется более эффективным, чем O (| S | ^ 2), но я не совсем уверен в его сложности. Вот грубая схема:

• Полоса ведущего a's, сохраняющая в переменной start.
• Сгруппируйте остальную часть строки в куски писем.
• Найдите индексы групп с самыми длинными последовательностями a's.
• Если осталось только один index, перейдите к 10.
• Отфильтруйте эти индексы так, чтобы длина [первой] группы b's после разворота была минимальной.
• Если осталось только один index, перейдите к 10.
• Отфильтруйте эти индексы так, чтобы длина [первой] группы a's (не включая начальную a's) после разворота была минимальной.
• Если осталось только один index, перейдите к 10.
• Вернитесь к 5, за исключением проверки групп [second/third/...] a's и b's на этот раз.
• Возвращает start, а также группы с отменой до index, а также остальные группы.

Так как любая подстрока, которая обращается вспять, начинается с a b и заканчивается на a, никакие два гипотетических разворота не являются палиндромами, и, следовательно, два разворота не приведут к одному и тому же результату, гарантируя, что существует уникальное оптимальное решение и что алгоритм завершится.

Моя интуиция говорит о таком подходе, вероятно, о (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 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'

Ответ 2

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

• Итерируйте по строке и обновите ее значение, интерпретируемое как двоичное число обратного (lsb-to-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);