Максимально увеличить сумму частот K выбранных символов из заданной строки

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

Примеры:

Input: K – 3, S = ”GEEKSFORGEEKS”
Output: 12
Explanation:
Choose the character E from the given string S, the sum of frequency of 3 E’s is 3*4 = 12, which is the maximum.

Input: K = 10, S = ”GEEKSFORGEEKS”
Output: 28

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

• Инициализируйте переменную, скажем, sum равным 0 , которая хранит результирующую сумму частот ровно K выбранных символов из строки S .
• Найдите частоты каждого символа в строке S и сохраните их во вспомогательном массиве, скажем, freq[] .
• Отсортируйте массив freq[] по убыванию.
• Перейдите массив freq[] и выполните следующее:
  • Если текущая частота меньше, чем K , то добавьте freq[i]*freq[i] к переменной sum , так как это максимизирует результирующую сумму и уменьшает значение freq[i] от K по мере выбора символов freq[i] .
  • В противном случае добавьте значение K*freq[i] к переменной sum и прервите цикл, так как было выбрано K символов.
• После выполнения вышеуказанных шагов выведите значение суммы в качестве результата.

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

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