Минимизируйте шаги для формирования строки S из любой случайной строки длины K с использованием подпоследовательностей фиксированной длины.

Для заданной строки S , состоящей из N символов и положительного целого числа K , задача состоит в том, чтобы найти минимальное количество операций, необходимых для генерации строки S из случайной строки temp размера K и вставки подпоследовательности любой фиксированной длины из случайной строки. в случайной строке. Если невозможно сгенерировать строку S , то выведите «-1» .

Примеры:

Input: S = “toffee”, N = 4
Output: 2 tofe
Explanation:
Consider the random string temp as “tofe” which is of length K(= 4) and perform the following steps:
Operation 1: Take a subsequence of length 1 from string temp as ‘f’ and after inserting the subsequence in the string “tofe” modifies the string to “toffe”.
Operation 2: Take a subsequence of length 1 from string temp as ‘e’ and after inserting the subsequence in the string “toffe” modifies the string to “toffee”.

Therefore, the minimum number of operations required is 2.

Input: S = “book”, N = 2
Output: -1

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

• Инициализировать ан массив, скажем, amount[] , который хранит частоту каждого символа строки S .
• Выполните итерацию в диапазоне [0, N – 1], используя переменную i , и увеличьте частоту текущего символа на 1 в массиве amount[] .
• Найдите count уникальных символов в строке S и сохраните его в переменной, скажем, count .
• Если количество больше N, верните -1 .
• Теперь выполните двоичный поиск, чтобы найти результирующую строку, и выполните следующие шаги:
• Инициализируйте две переменные со значением 10 ⁵ и значением 0 .
• Повторяйте до тех пор, пока значение (высокий – низкий) не станет больше 1 , и выполните следующие шаги:
  • Обновите значение total как 0 и mid как (high + low) / 2 .
  • Выполните итерацию в диапазоне [0, 25], используя переменную i , и если значение amount[i] больше 0 , то увеличьте итог на (amounts[i] – 1)/mid + 1 .
  • Если общая сумма меньше, чем равна N , затем обновите значение high как mid . В противном случае обновите значение low как mid .
• После выполнения вышеуказанных шагов выведите значение high anditerate в диапазоне [0, 25] и выведите результирующую строку.

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

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