Partition Labels

+10

Дана строка s из строчных букв. Разбейте её на как можно больше последовательных частей так, чтобы каждая буква встречалась только в одной части: если буква встречается в части, все её вхождения должны быть в этой части. Верните длины частей слева направо.

Функция

partitionLabels(s: string) → integer-array

sstring: строка для обрезки, только строчные буквы
Возвращаетinteger-array: длина каждой части слева направо

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит только строчные английские буквы.
Эти части сохраняют свой порядок и вместе составляют всё s, поэтому их длины в сумме равны s.length.

Примеры

Ввод: s = "abacdcefe"
Вывод: [3, 3, 3]
Пояснение: Буквы a находятся на позициях 0 и 2, c — на позициях 3 и 5, а e — на позициях 6 и 8, поэтому разрезы проходят после aba и после cdc. Ни одну часть нельзя разрезать снова, потому что каждая начинается и заканчивается одной и той же буквой.

+14 скрытых тестов при отправке

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Разрез допустим только там, где по обе стороны от него нет одинаковой буквы, а лучший ответ — разрезать в каждом таком месте. Проверка каждого места повторным просмотром строки требует квадратичного времени. Сначала запишите последнюю позицию каждой буквы, и один проход слева направо позволит найти все разрезы, потому что часть должна продолжаться до последнего вхождения каждой буквы в неё.

Проверьте каждый пробел

Верно, но не успевает на самых больших тестах

Идея

Между соседними буквами есть n-1 промежутков. Разрезать можно только в том промежутке, по обе стороны от которого не встречается одна и та же буква: если разрез разделит букву, она окажется в двух частях. Если сделать разрез в каждом подходящем промежутке, получится максимальное число частей. Рассмотрим часть между двумя соседними подходящими промежутками: ни одна из её букв не встречается левее левого разреза или правее правого, поэтому все её копии находятся внутри этой части, и она подходит. А в любом допустимом ответе разрезы могут быть только в подходящих промежутках, поэтому частей не может быть больше.

Проверяй каждый промежуток: собери буквы слева и справа от него и делай разрез, если множества не пересекаются. В abacdcefe после aba слева находятся буквы a и b, а справа — c, d, e и f. Общих букв нет, значит, здесь можно разрезать. После ab буква a встречается с обеих сторон, поэтому здесь разрезать нельзя.

Для каждой проверки нужно прочитать всю строку, а промежутков n-1, поэтому потребуется примерно n² чтений букв. При длине строки 50 000 это 2.5 × 10^9 чтений — слишком медленно для самых больших тестов.

Алгоритм

Задай start = 0 — место, где начинается текущая часть.
Для каждого разрыва cut от 1 до n-1 (разрыв непосредственно перед s[cut]) отметь буквы s[0..cut-1] и буквы s[cut..n-1].
Если ни одна буква не отмечена с обеих сторон, добавь cut-start к ответу и задай start = cut.
После цикла добавь последнюю часть: n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Объедините диапазоны каждой буквы

Идея

Представь каждую букву как интервал — от её первой позиции до последней. Часть, содержащая букву, должна охватывать весь этот интервал. Поэтому две буквы, интервалы которых пересекаются, должны находиться в одной части, а пересечение распространяется дальше: если a пересекается с b, а b пересекается с c, все три в итоге окажутся в одной части.

Это задача об объединении интервалов. За один проход запиши первую и последнюю позицию каждой буквы. Затем возьми интервалы в порядке их начальных позиций и объедини те, которые пересекаются. Каждый объединённый блок — это одна часть, а промежутки между блоками — это и есть допустимые разрезы. Интервалы уже будут расположены в порядке начальных позиций, сортировка не нужна: пройди по строке ещё раз и бери интервал буквы, когда дойдёшь до её первой позиции.

В codingisfun интервалы в порядке следования: c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] и u [9, 9]. Первые три не пересекаются с другими. Начиная с i, каждый интервал начинается не позже позиции 10, где заканчивается интервал n, поэтому они объединяются в [3, 10] — часть из 8 букв.

В строке не более 26 различных букв, поэтому интервалов не более 26, а таблицы первых и последних позиций имеют фиксированный размер.

Алгоритм

За один проход по s запишите first и last — первую и последнюю позиции каждой буквы.
Снова пройдите по s. Если позиция i — первая позиция своей буквы, интервал этой буквы [i, last] будет следующим по порядку начала.
Если интервал начинается после end текущего блока, закройте блок длиной end-start+1 и начните новый блок с i.
В любом случае задайте end = max(end, last).
Закройте последний блок и верните длины.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Увеличивайте каждую часть до последней буквы

Идея

Первые позиции вовсе не нужны. Читай строку слева направо и храни end — самую дальнюю последнюю позицию любой буквы в текущей части. Когда ты читаешь букву на позиции i, её последнее вхождение тоже должно быть в этой части, поэтому увеличь end до last[s[i]], если это значение больше.

Когда i достигает end, у каждой буквы, прочитанной в этой части, последнее вхождение находится на позиции i или раньше. Ни одна буква не пересекает границу после i, поэтому здесь можно сделать разрез. Заверши часть длины end-start+1 и начни следующую с i+1.

Почему жадный выбор — сделать разрез при первой возможности? Пока i не достигло end, у какой-то буквы из этой части ещё есть вхождение правее, поэтому раньше разрезать нельзя. И алгоритм не пропускает ни одной допустимой границы: если ни одна буква не пересекает границу после i, последнее вхождение каждой буквы из части находится на позиции i или раньше, поэтому прямо здесь end равно i. Алгоритм делает разрезы ровно на допустимых границах, что даёт максимально возможное число частей.

В строке abacdcefe последние позиции: a — 2, b — 1, c — 5, d — 4, e — 8 и f — 7. При чтении a значение end становится равным 2, b оставляет его без изменений, а при i = 2 часть завершается и имеет длину 3. Буква c устанавливает end в 5, и часть завершается на позиции 5, снова имея длину 3. Часть с e завершается на позиции 8.

Алгоритм

За один проход сохраните last[c] — последнюю позицию каждой буквы c — в массиве из 26 элементов.
Установите start = 0 и end = 0.
Для каждой позиции i установите end = max(end, last[s[i]]).
Если i == end, добавьте end-start+1 к ответу и установите start = i+1.
Верните длины.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Ловушки и крайние случаи

Жадный проход короткий, поэтому ошибки скрываются в том, с какой позицией вы сравниваете, и в длинах частей.

Разрезать, когда вы доходите до последнего вхождения текущей буквы, вместо конца части end. В abcba буква c с индексом 2 — её последнее вхождение, но буквы a встречаются до индекса 4, поэтому разрез в этом месте разделил бы и a, и b.
Ошибка на единицу в длине. Часть от start до end, включая обе границы, содержит end-start+1 букв.
Возвращать позиции разрезов вместо длин. Для abacdcefe ответ — [3, 3, 3], а не [2, 5, 8].
Забыть о последней части, если вы разрезаете в промежутках. После последней части промежутка нет, поэтому после завершения цикла добавьте n-start.
Ожидать по одной части на каждую уникальную букву. В zebraz пять разных букв и одна часть, потому что буквы z соединяют всё, что находится между ними.

Частые вопросы4

Какова временная сложность алгоритма Partition Labels?

В одном проходе записывается последняя позиция каждой буквы, а во втором проходе расставляются разрезы, поэтому время выполнения составляет O(n). Таблица последних позиций содержит 26 элементов независимо от длины строки, поэтому дополнительные затраты памяти составляют O(1), не считая результата.

Почему жадный подход работает для задачи разбиения на метки?

Текущая часть должна доходить до последнего вхождения каждой буквы, которая в ней содержится, поэтому разрезать до end нельзя. На позиции end ни одна буква этой части больше не встречается, поэтому разрезать можно, и это никак не повредит оставшейся части строки. Таким образом, проход выполняет разрез на каждом допустимом промежутке и нигде больше, благодаря чему ответ содержит максимально возможное количество частей.

Задача Partition Labels — это задача на объединение интервалов?

Да, в замаскированном виде. Каждая буква охватывает интервал от своего первого появления до последнего; перекрывающиеся интервалы должны иметь общую часть, а их объединение даёт в точности эти части. Жадный проход — это то же объединение, выполненное на лету: end — правая граница объединённого блока на данный момент.

Сколько частей может вернуть Partition Labels?

От 1 до 26. Одна и та же буква не может встречаться в двух частях, поэтому у каждой части есть хотя бы одна собственная буква, а строчных букв всего 26. Строка, в которой каждая буква встречается один раз, даёт 26 частей длиной 1, а строка, которая начинается и заканчивается одной и той же буквой, состоит из одной части.

Python

def partitionLabels(s):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "abacdcefe"

Ожидается

[3, 3, 3]

Partition Labels

Функция

Ограничения

Примеры

Подсказки

Решение

Проверьте каждый пробел

Объедините диапазоны каждой буквы

Увеличивайте каждую часть до последней буквы

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи