Минимизируйте удаления так, чтобы сумма позиций символов не превышала K
Для заданной строки 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)