Минимизируйте операции по удалению всех элементов перестановки A, удалив подпоследовательность, имеющую порядок как массив B

Для заданных двух массивов перестановок A[] и B[] из первых N натуральных чисел задача состоит в том, чтобы найти минимальное количество операций, необходимых для удаления всех элементов массива A[] , чтобы в каждой операции удалялась подпоследовательность элементов массива A[ ] порядок которых такой же, как в массиве B[] .

Пример:

Input: A[] = { 4, 2, 1, 3 }, B[] = { 1, 3, 2, 4 }
Output: 3
Explanation:
The given example can be solved by following the given steps:

1. During the 1st operation, integers at index 2 and 3 in the array A[] can be deleted. Hence, the array A[] = {4, 2}.
2. During the 2st operation, integer at index 1 in the array A[] can be deleted. Hence, the array A[] = {4}.
3. During the 3rd operation, integer at index 0 in the array A[] can be deleted. Hence, the array A[] = {}.

The order in which the elements are deleted is {1, 3, 2, 4} which is equal to B. Hence a minimum of 3 operations is required.

Input: A[] = {2, 4, 6, 1, 5, 3}, B[] = {6, 5, 4, 2, 3, 1}
Output: 4

Подход: Данная проблема может быть решена с помощью шагов, описанных ниже:

1. Создайте две переменные i и j , где i отслеживает индекс текущего элемента B , который должен быть удален следующим, а j отслеживает текущий элемент A. Изначально оба i=0 и j=0 .
2. Пройдите массив перестановок A[] , используя j для всех значений j в диапазоне [0, N-1] . Если A[j] = B[i] , увеличьте значение i на 1 и продолжите обход массива A[] .
3. После полного обхода массива A[] увеличьте значение переменной cnt , которая поддерживает количество требуемых операций.
4. Повторяйте шаги 2 и 3 , пока i<N .
5. После выполнения вышеуказанных шагов значение, хранящееся в cnt , является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)