Ctrl K

Перестановки по связям

Средняя
Дана строка text из строчных латинских букв и список связей links, где каждая связь [a, b] — пара позиций в строке (нумерация с нуля). Буквы на позициях любой связи можно менять местами, причём сколько угодно раз и в любом порядке. Верните лексикографически наименьшую строку, которую можно получить из text такими обменами.
Пример 1
text="lkji", links=[[0, 2], [1, 3]] → 'jilk'

Меняем местами буквы на позициях 0 и 2 ("jkli"), затем на позициях 1 и 3 — получаем "jilk".

Пример 2
text="post", links=[[0, 1], [1, 3]] → 'opst'

Позиции 0, 1 и 3 связаны цепочкой, их буквы p, o, t можно расставить как угодно: o, p, t. Буква s на позиции 2 остаётся на месте.

Пример 3
text="ba", links=[] → 'ba'

Связей нет — менять ничего нельзя.

Ограничения
  • 1 ≤ len(text) ≤ 10⁵
  • 0 ≤ len(links) ≤ 10⁵
  • 0 ≤ links[i][0], links[i][1] < len(text)
  • text состоит из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСклеить карточки контактов СредняяЦепочки синонимов СредняяСемейства слов на один обмен СложнаяЦепочки отношений СредняяПоле, разрезанное чертами Средняя
загружаем Python…
Вход
text="lkji", links=[[0, 2], [1, 3]]
Ожидается
'jilk'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 77 тестов на сервере, включая скрытые.