Минимизируйте удаления так, чтобы сумма позиций символов не превышала K

Опубликовано: 27 Февраля, 2023

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

Примеры :

Input: S = “abca”, K = 2
Output: “aa”
Explanation: Initial sum for the given string is 1 + 2 + 3 + 1 = 7 
(since positions of a, b, and c are 1, 2, and 3 respectively). 
If we remove b and c from the string “abca”, it becomes “aa”,  
having cost 2 which is less than or equal to the given K.

Input: S = “geeksforgeeks”, K= 27
Output: “eefee”

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

The main observation is that first, we must remove the characters having maximum cost before removing the characters having lesser cost. 

  • Сначала создайте переменную (например, totalCost ) для хранения общей стоимости исходной строки S.
  • Затем создайте копию строки S (скажем, temp ) и отсортируйте ее в обратном порядке символов.
  • Пройдите через temp и продолжайте сохранять символы в карте (скажем, del ), пока totalCost не станет больше, чем K .
    • Эти символы, хранящиеся на карте, в основном являются символами, которые необходимо удалить.
  • Наконец, пройдитесь по строке S , удалите символы, хранящиеся в карте del , и верните окончательную строку.

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

Временная сложность : O (N * log (N)), где N — длина строки.
Вспомогательное пространство : O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ