Минимум операций не требуется для создания строки A Путем добавления подпоследовательности строки B к пустой строке C

Question

Вы дали две строки A и B. У вас есть некоторая пустая строка C. За одну операцию Вы можете удалить любое количество символов (из любого места) из строки B и добавить его к строке C. Минимум операций не требуется для преобразования Строка C в строку A.

например, если А является "ABCDE" и B "ABDEC" тогда В 1-й операции вы выберете подпоследовательность ABC из B, а во 2-й операции DE.

Итак, требуется две операции.

если А - это "ABCDE" B является "EDCBA" тогда необходимые операции 5 .

Ожидаемая линейная сложность O (n)

Answer 1

Просто используйте жадный алгоритм.

1 - Пусть i = 0
2 - Пусть j = 0
3 - Поиск первого A[i] в B после j
4 - Если он существует, пусть j будет его индексом в B, удалите его из B, добавьте его к C, увеличьте i и повторите с 3
5 - Если его не существует, повторите с 2

Каждый раз, когда вы получаете 5 соответствует одной операции.

Если предположить, что все символы A (и B) различны, то вот решение с линейной сложностью. Вам нужна хэш-карта или что-то подобное, а также массив индексов, Y, равной длины A и B.

1 - Поместить каждый символ A в хэш-карту в качестве ключа с индексом в качестве значения.
2 - Найдите каждый символ B в хэш-карте, чтобы получить значение i, и поместите его индекс в Y в позиции i.
3 - Пройдите Y, считая количество раз, которое Y[i] < Y[i-1]. Это ваше количество операций.