# Maximize frequency sum of K chosen characters from given string

Given a positive integer **K **and a string **S** consisting of **N** characters, the task is to maximize the sum of the frequencies of exactly K chosen characters from the given string.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:K – 3, S = ”GEEKSFORGEEKS”Output:12Explanation:

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

**Approach:** The given problem can be solved by using the Greedy Approach by choosing those **K characters** having the higher frequencies. Follow the steps below to solve the problem:

- Initialize a variable, say
**sum**to**0**that stores the resultant sum of frequencies of exactly K chosen characters from the string**S**. - Find the frequencies of each character in the string
**S**and store it in an auxiliary array, say**freq[]**. - Sort the array
**freq[]**in descending order. - Traverse the array
**freq[]**and perform the following:- If the current frequency is less than
**K**, then add**freq[i]*freq[i]**to the variable**sum**as it maximizes the resultant sum and decrements the value of**freq[i]**from**K**as**freq[i]**characters are chosen. - Otherwise, add the value of
**K*freq[i]**to the variable**sum**and break out of the loop as**K**characters have been chosen.

- If the current frequency is less than
- After completing the above steps, print the value of the
**sum**as the result.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the maximum sum of` `// frequencies of the exactly K chosen` `// characters from the string S` `int` `maximumSum(string S, ` `int` `N, ` `int` `K)` `{` ` ` `// Stores the resultant maximum sum` ` ` `int` `sum = 0;` ` ` `// Stores the frequency of array` ` ` `// elements` ` ` `int` `freq[256] = { 0 };` ` ` `// Find the frequency of character` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `freq[` `int` `(S[i])]++;` ` ` `}` ` ` `// Sort the frequency array in the` ` ` `// descending order` ` ` `sort(freq, freq + 256, greater<` `int` `>());` ` ` `// Iterate to choose K elements greedily` ` ` `for` `(` `int` `i = 0; i < 256; i++) {` ` ` `// If the freq[i] cards are` ` ` `// chosen` ` ` `if` `(K > freq[i]) {` ` ` `sum += freq[i] * freq[i];` ` ` `K -= freq[i];` ` ` `}` ` ` `// K cards have been picked` ` ` `else` `{` ` ` `sum += freq[i] * K;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` `}` `// Driver Code` `int` `main()` `{` ` ` `string S = ` `"GEEKSFORGEEKS"` `;` ` ` `int` `K = 10;` ` ` `int` `N = S.length();` ` ` `cout << maximumSum(S, N, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG` `{` `// Function to find the maximum sum of` `// frequencies of the exactly K chosen` `// characters from the String S` `static` `int` `maximumSum(String S, ` `int` `N, ` `int` `K)` `{` ` ` ` ` `// Stores the resultant maximum sum` ` ` `int` `sum = ` `0` `;` ` ` `// Stores the frequency of array` ` ` `// elements` ` ` `Integer []freq = ` `new` `Integer[` `256` `];` ` ` `Arrays.fill(freq, ` `0` `);` ` ` `// Find the frequency of character` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++)` ` ` `{` ` ` `freq[(` `int` `)S.charAt(i)] += ` `1` `;` ` ` `}` ` ` `// Sort the frequency array in the` ` ` `// descending order` ` ` `Arrays.sort(freq, Collections.reverseOrder());` ` ` `// Iterate to choose K elements greedily` ` ` `for` `(` `int` `i = ` `0` `; i < ` `256` `; i++)` ` ` `{` ` ` ` ` `// If the freq[i] cards are` ` ` `// chosen` ` ` `if` `(K > freq[i])` ` ` `{` ` ` `sum += freq[i] * freq[i];` ` ` `K -= freq[i];` ` ` `}` ` ` `// K cards have been picked` ` ` `else` ` ` `{` ` ` `sum += freq[i] * K;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` `}` `// Driver Code` `public` `static` `void` `main(String args[])` `{` ` ` `String S = ` `"GEEKSFORGEEKS"` `;` ` ` `int` `K = ` `10` `;` ` ` `int` `N = S.length();` ` ` ` ` `System.out.print(maximumSum(S, N, K));` `}` `}` `// This code is contributed by ipg2016107` |

## Python3

`# Python3 program for the above approach` `# Function to find the maximum sum of` `# frequencies of the exactly K chosen` `# characters from the string S` `def` `maximumSum(S, N, K):` ` ` ` ` `# Stores the resultant maximum sum` ` ` `sum` `=` `0` ` ` `# Stores the frequency of array` ` ` `# elements` ` ` `freq ` `=` `[` `0` `] ` `*` `256` ` ` ` ` `# Find the frequency of character` ` ` `for` `i ` `in` `range` `(N):` ` ` `freq[` `ord` `(S[i])] ` `+` `=` `1` ` ` `# Sort the frequency array in the` ` ` `# descending order` ` ` `freq ` `=` `sorted` `(freq)[::` `-` `1` `]` ` ` `# Iterate to choose K elements greedily` ` ` `for` `i ` `in` `range` `(` `256` `):` ` ` ` ` `# If the freq[i] cards are` ` ` `# chosen` ` ` `if` `(K > freq[i]):` ` ` `sum` `+` `=` `freq[i] ` `*` `freq[i]` ` ` `K ` `-` `=` `freq[i]` ` ` ` ` `# K cards have been picked` ` ` `else` `:` ` ` `sum` `+` `=` `freq[i] ` `*` `K` ` ` `break` ` ` `# Return the resultant sum` ` ` `return` `sum` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `S ` `=` `"GEEKSFORGEEKS"` ` ` `K ` `=` `10` ` ` `N ` `=` `len` `(S)` ` ` ` ` `print` `(maximumSum(S, N, K))` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` ` ` `// Function to find the maximum sum of` `// frequencies of the exactly K chosen` `// characters from the string S` `static` `int` `maximumSum(` `string` `S, ` `int` `N, ` `int` `K)` `{` ` ` ` ` `// Stores the resultant maximum sum` ` ` `int` `sum = 0;` ` ` `// Stores the frequency of array` ` ` `// elements` ` ` `int` `[]freq = ` `new` `int` `[256];` ` ` `Array.Clear(freq, 0, 256);` ` ` `// Find the frequency of character` ` ` `for` `(` `int` `i = 0; i < N; i++)` ` ` `{` ` ` `freq[(` `int` `)S[i]]++;` ` ` `}` ` ` `// Sort the frequency array in the` ` ` `// descending order` ` ` `Array.Sort(freq);` ` ` `Array.Reverse(freq);` ` ` `// Iterate to choose K elements greedily` ` ` `for` `(` `int` `i = 0; i < 256; i++)` ` ` `{` ` ` ` ` `// If the freq[i] cards are` ` ` `// chosen` ` ` `if` `(K > freq[i])` ` ` `{` ` ` `sum += freq[i] * freq[i];` ` ` `K -= freq[i];` ` ` `}` ` ` `// K cards have been picked` ` ` `else` ` ` `{` ` ` `sum += freq[i] * K;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `string` `S = ` `"GEEKSFORGEEKS"` `;` ` ` `int` `K = 10;` ` ` `int` `N = S.Length;` ` ` ` ` `Console.Write(maximumSum(S, N, K));` `}` `}` `// This code is contributed by ipg2016107` |

## Javascript

`<script>` `// JavaScript program for the above approach` `// Function to find the maximum sum of` `// frequencies of the exactly K chosen` `// characters from the string S` `function` `maximumSum(S, N, K)` `{` ` ` ` ` `// Stores the resultant maximum sum` ` ` `let sum = 0;` ` ` `// Stores the frequency of array` ` ` `// elements` ` ` `let freq = Array.from({length: 256}, (_, i) => 0);` ` ` `// Find the frequency of character` ` ` `for` `(let i = 0; i < N; i++)` ` ` `{` ` ` `freq[S[i].charCodeAt()]++;` ` ` `}` ` ` `// Sort the frequency array in the` ` ` `// descending order` ` ` `freq.sort((a, b) => b - a);` ` ` `// Iterate to choose K elements greedily` ` ` `for` `(let i = 0; i < 256; i++)` ` ` `{` ` ` ` ` `// If the freq[i] cards are` ` ` `// chosen` ` ` `if` `(K > freq[i])` ` ` `{` ` ` `sum += freq[i] * freq[i];` ` ` `K -= freq[i];` ` ` `}` ` ` `// K cards have been picked` ` ` `else` ` ` `{` ` ` `sum += freq[i] * K;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` `} ` `// Driver Code` ` ` `let S = ` `"GEEKSFORGEEKS"` `;` ` ` `let K = 10;` ` ` `let N = S.length;` ` ` ` ` `document.write(maximumSum(S.split(` `''` `), N, K))` `</script>` |

**Output:**

28

**Time Complexity:** O(N)**Auxiliary Space:** O(26)