Ввод 4 ---! !---

Ответ: 3

Пошаговое решение и объяснение:

• Дан вход:

  • n = 4
  • s = "---!"
  • t = "!---" Оба строка содержат ровно по одному символу '!' и три символа '-'.

• Мы хотим минимальное число обменов соседних символов (модуль перестановок соседних) чтобы преобразовать s в t.

• Правило: если в s и t одинаковое количество восклицательных знаков (!), минимальное число swaps равно сумме по всем i от 1 до k (k — число '!') |pos_s[i] - pos_t[i]|, где pos_s и pos_t — позиции '!' в s и t соответственно (последовательно отсортированы). Это потому что переставлять соседние символы перемещает каждый '!' на одну позицию за обмен, и мы сохраняем относительный порядок нескольких '!' (что минимизирует суммарное перемещение).

• Применяем к данному примеру:

  • Позиции '!' в s: pos_s = [4]
  • Позиции '!' в t: pos_t = [1]
  • Сумма: |4 - 1| = 3

• Визуальная иллюстрация перемещений: ---! -> swap 3-4 -> --!- --!- -> swap 2-3 -> -!-- -!- - -> swap 1-2 -> !--- Всего 3 обмена.

Итого, минимальное число соседних обменов для перехода от "---!" к "!---" равно 3.