Минимальная стоимость построения подпоследовательности длины K из заданной строки S

Для заданной строки S , состоящей из N строчных букв латинского алфавита, целого числа K и массива cost[] размера 26 , обозначающего стоимость каждого строчного английского алфавита, задача состоит в том, чтобы найти минимальную стоимость построения подпоследовательности длины K из персонажи строки S .

Примеры:

Input: S = “aabcbc”, K = 3, cost[] = {2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}
Output: 4
Explanation:
One way to construct a string of size K(= 3) is:
Form the string “abb” taking two ‘b’s with a cost of (2*1 = 2), and one ‘a’ with a cost of (1*2 = 2).
Therefore, the total cost to construct the string “abb” is (2 + 2 = 4), which is the minimum possible.

Input: S = “aaaca”, K = 1, cost[] = {2, 1, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}
Output: 2

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

• Инициализируйте вектор пары char и int, скажем, V для хранения символа и стоимость этого персонажа.
• Кроме того, инициализируйте карту, скажем, mp с ключом в виде символа и значением в виде целых чисел, чтобы сохранить частоту каждого символа строки S .
• Пройдите по заданной строке, используя переменную i , и на каждой итерации увеличивайте значение mp[S[i]] .
• Переберите диапазон [0, 25], используя переменную i , и на каждой итерации добавьте пару {char('a' + i), cost[i]} к вектору пар V .
• Отсортируйте вектор пар V[]по второму элементу пары.
• Теперь инициализируйте переменную, скажем, minCost как 0 , чтобы сохранить минимальную стоимость подпоследовательности длины K.
• Переберите диапазон [0, 25], используя переменную i , и выполните следующие шаги:
  • Инициализировать переменную, скажем, считать как mp['a' + i] .
  • Если значение count меньше K , то добавьте значение count*V[i].second к значению minCost и обновите значение K до K – count .
  • В противном случае добавьте K*V[i].second к значению minCost и прервите цикл.
• После выполнения вышеуказанных шагов выведите в качестве результата значение minCost .

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

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