Минимизируйте удаления, чтобы уменьшить String до размера 1, при этом с удалением можно удалить N/2^i вхождений (X+i-1)-го символа.

Для заданной строки str длины N и символа X , где N всегда имеет форму 2 ^k , задача состоит в том, чтобы найти минимальные операции замены, необходимые для уменьшения размера строки до 1 , где i ^-е удаление, N/2 ⁱ вхождения (X + i – 1) ^-го символа могут быть удалены либо с начала, либо с конца строки.

Пример:

Input: str = “CDAAAABB”, X = ‘A’
Output: 4
Explanation: Replacement operations on the given string can be done as:

1. Replace ‘C’ at 1st index with ‘A’.
2. Replace ‘D’ at 2nd index with ‘A’.
3. Replace ‘A’ at 5th index with ‘D’.
4. Replace ‘A’ at 6th index with ‘C’.

Therefore, the string becomes str = “AAAADCBB”. During the 1st deletion (8/2¹) occurrences of (A+1-1)^th character can be removed from the front of the string. Therefore, the string becomes str = “DCBB”. Similarly, during the 2nd deletion (8/2²) occurrences of (A+2-1)^th  i.e, ‘B’ character can be removed from the back of the string. Therefore, the string becomes str = “DC”. Similarly, after the 3rd deletion, the string becomes str = “D” having length as 1. Therefore, the number of required replacement operations are 4 which is the minimum possible.

Input: str = “QRQP”, X = ‘P’
Output: 1

Подход: Данную проблему можно решить, используя рекурсию, имеющую аналогичную структуру бинарного поиска. Во время каждого удаления можно заметить, что есть 2 возможных варианта. Они следующие:

1. Замените все символы первой половины заданной строки на «X» и рекурсивно вызовите оставшуюся половину для X = X + 1.
2. Или замените все символы второй половины заданной строки на «X» и рекурсивно вызовите оставшуюся половину для X = X + 1.

Поэтому, используя приведенные выше наблюдения, создайте рекурсивную функцию, которая берет минимальные ходы из двух возможностей, вычисляя количество индексов, которые необходимо заменить на X в первой половине строки, и рекурсивно вызывая оставшуюся половину и наоборот. .

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

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