# Maximize the String value by assigning values in range [1, 26] to each character

Given a string **S** of size **N**, the task is to find the maximum sum of values assigned to all the alphabets of the string **S**. The value assigned to all the characters are over the range **[1, 26]**, and the values assigned to the same lowercase and uppercase character is the same.

**Examples:**

Input:S = “pQrqQPR”Output:176Explanation:

The value of the letter ‘P’ is taken as 25, ‘Q’ is taken as 26, ‘R’ is taken as 24. Now, the sum of values assigned to the characters of the string is 25 + 26 + 24 + 26 + 26 + 25 + 24 = 176, which is maximum among all possible combinations of assigining values.

Input:S = “#aAaa$”Output:104

**Approach:** The given problem can be solved by storing the frequency of the alphabets in a frequency array and sorting them in descending order. The idea is to multiply the highest frequency with **26**, 2^{nd} highest frequency with **25**, and so on. Follow the steps below to solve the given problem:

- Initialize an auxiliary array, say
**frequency[]**that stores the frequency of distinct characters in the string**S**. - Traverse the string and at every iteration, if the character
**ch**, then increment the frequency using the following cases:**Upper Case:**increment the value at**frequency[ch – ‘A’]**.**Lower Case:**increment the value at**frequency[ch – ‘a’]**.**Special Character:**continue the loop.

- Sort the array
**frequency[]**in increasing order. - Initialize a variable, say
**sum**as**0**to store the value of the string. - Traverse the array in reverse order using a variable
**i**from index**25**to**0**, and at every iteration perform the following steps:- If the value at
**frequency[i]**is**0**, then break the loop. - Otherwise, multiply the value of
**frequency[i]**with**i**and add it to the variable**sum**.

- If the value at
- After 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 max possible sum ` `// of values assigned to each characters ` `// of the given string ` `int` `maxStrength(string s) ` `{ ` ` ` `// Initialize a frequency array of ` ` ` `// size 26 with all elements as 0 ` ` ` `vector<` `int` `> frequency(26, 0); ` ` ` ` ` `for` `(` `char` `ch : s) { ` ` ` ` ` `// Lowercase character ` ` ` `if` `(ch >= ` `'a'` `&& ch <= ` `'z'` `) { ` ` ` `frequency[ch - ` `'a'` `]++; ` ` ` `} ` ` ` ` ` `// Uppercase character ` ` ` `else` `if` `(ch >= ` `'A'` `&& ch <= ` `'Z'` `) { ` ` ` `frequency[ch - ` `'A'` `]++; ` ` ` `} ` ` ` `} ` ` ` ` ` `// Sort the frequency array ` ` ` `sort(frequency.begin(), ` ` ` `frequency.end()); ` ` ` ` ` `// Stores the maximum sum of value ` ` ` `int` `ans = 0; ` ` ` ` ` `for` `(` `int` `i = 25; i >= 0; i--) { ` ` ` ` ` `// If the frequency of the ` ` ` `// current character is > 0 ` ` ` `if` `(frequency[i] > 0) { ` ` ` `ans = ans + frequency[i] * (i + 1); ` ` ` `} ` ` ` ` ` `// Otherwise ` ` ` `else` ` ` `break` `; ` ` ` `} ` ` ` ` ` `// Return the maximum sum obtained ` ` ` `return` `ans; ` `} ` ` ` `// Driver Code ` `int` `main() ` `{ ` ` ` `string S = ` `"pQrqQPR"` `; ` ` ` `cout << maxStrength(S); ` ` ` ` ` `return` `0; ` `}` |

**Output:**

176

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

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**.