Переместите любой символ из одной строки в конец, найдите хотя бы сколько ходов вы можете сделать, чтобы две строки стали одной строкой

Question

Сегодня я занимаюсь некоторой практикой кодирования и столкнулся с этим вопросом, на котором я не смог найти подход к решению этого вопроса. Может ли кто-нибудь поделиться своим пониманием этой проблемы?

---

---

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

Можно предположить, что S, T имеют одинаковую длину с одинаковыми символами.

Пример:
S: cadb T: abcd Вывод: 2

Объяснение: 1. Сначала переместите 'c' в конец, затем S стал "adb c" 2. Переместите 'd' в конец, после чего S станет "abcd", что аналогично T.

---

---

Может быть, DFS или BFS помогут? Я не знаю ...

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

Answer 1

Когда вы закончите, символы, которые вы не перемещаете, появятся раньше, чем все символы, которые вы делаете , и они будут соответствовать префиксу целевой строки.

Чтобы переместить минимальное количество символов, найдите самую длинную подпоследовательность S, которая является префиксом T. Затем переместите все остальные в правильном порядке, чтобы соответствовать остальной части T. Если вы не можете, то там совпадение невозможно.

Легко сделать - вы просто находите символы из T в S по порядку:

T:  lookingForThis
S:  ThiloFokrinsgo
       ^^ ^^ ^^ ^ 
Keep: looking
Move:        ForThis