C++ 将字符串值最大化，将值范围在[1, 26]内分配给每个字符

英语中存在26个不同的字母。如果我们想将字母字符转换为数字值，则需要将字母的值分配在1到26之间。

现在，在这个问题中，我们需要通过将每个字符的值分配在[1, 26]的范围内来最大化字符串值。让我们看看我们应该如何解决这个问题。

让我们通过一些示例来了解这个问题。

输入 – s = “blpsBpPtT”

输出 – 221

解释 – 在这里，为了最大化给定字符串的值，我们将分配：

• p，P的值为26

• b，B的值为25

• t，T的值为24

• l的值为23

• s的值为22

因此，最后输出为((26 * 3) + (25 * 2) + (24 * 2) + (23 * 1) + (22 * 1))，即221。

输入 – s = “Aa$#&*@!Bsbb”

输出 – 152

解释 – 在这里，为了最大化给定字符串的值，我们将分配：

• b，B的值为26

• a，A的值为25

• s的值为24

• 其余字符没有值，即值为零

因此，最后输出为((26 * 3) + (25 * 2) + (24 * 1))，即152。

问题解释

让我们试着理解问题并找到解决方案。在这个问题中，我们需要通过分配从1到26的值来最大化字符串的值，如果字符是字母，则范围为1到26，但如果不是字母，则为其他字符如’$’，’#’，’&’等，我们将取值为零。对于大写和小写字符，如果它们是相同类型的，例如’p’和’P’，我们将视为相同。我们可以通过将最常出现的字母字符分配最大值来快速最大化值。在下面的文章中，我们将看到两种存储频率的方法。

解决方案1 – 使用映射

步骤

• 定义一个名为 m 的映射。

• 运行循环来存储给定字符串的大写和小写字母的频率。

• 将频率推入一个向量中。

• 对包含频率的向量进行排序。

• 从后面开始，以26、25、24等的顺序将频率与数字相乘。

• 将相乘的值相加得到最终结果。

C++代码实现示例

#include <bits/stdc++.h>
using namespace std;
// Function to maximize the String value by assigning values in the range [1, 26] to each character
int Helper(string s){
   // Define a map to store the characters in it to count the frequency of each character
    map<int,int>m;
    // Run a loop to initiate the map
    for (int i=0;i<s.size();i++){
       char chr=s[i];
        // To store lowercase character
        if (chr >= 'a' && chr <= 'z') {
            m[chr - 'a']++;
        }
        // To store uppercase character
        else if (chr >= 'A' && chr <= 'Z') {
            m[chr - 'A']++;
        }
    }
    vector<int>v;
    // Push the frequencies in the vector
    for(auto a:m){
        v.push_back(a.second);
    }
    // Sort the frequencies
    sort(v.begin(),v.end());
    // Intialise ans variable
    int ans=0, num=26;
    // Get the answer in accordance with the frequencies and range [1, 26]
    for(int i=v.size()-1; i>=0; i--){
        // Add the highest frequency with num which is initially set to 26
        ans+=(num*v[i]);
        // Decrement num to move to the next largest frequency
        num--;
    }
    // Return the final output
    return ans;
}
int main(){
   // Give the input string
   string S = "aBAbgha";
   // Call the helper function to maximize the String value by assigning values in the range [1, 26] to each character
   cout << "The maximum string value by assigning values in the range [1, 26] to each character is: "<<Helper(S);
   return 0;
}

输出

The maximum string value by assigning values in the range [1, 26] to each character is: 175

上述代码的复杂性

• 时间复杂度 – O(n*(log(n)))；在这里我们使用了循环，但它们将运行’n’次，然而，排序函数将需要(n * log(n))时间来执行，因此我们将整体代码的复杂性设定为n * log(n)。

• 空间复杂度 – O(26)；因为英语中只有26个不同的字母。

解决方案2 – 使用频率向量

步骤

• 定义一个大小为26的向量v，并将所有初始值设为’0’。

• 运行一个循环来存储给定字符串中大写字母和小写字母的频率，并将其存储在向量中，现在称为频率向量。

• 对包含频率的向量进行排序。

• 从后面开始，将频率乘以26、25、24等，直到频率为’0’时停止循环。

• 将乘积值相加得到最终答案。

示例- C++代码实现

#include <bits/stdc++.h>
using namespace std;
// Function to maximize the String value by assigning values in the range [1, 26] to each character
int Helper(string s){
    // Define a frequency vector of size 26 with initial elements as 0
    vector<int> v(26, 0);
    // Run a loop to initiate the vector
    for (int i=0;i<s.size();i++){
        char chr=s[i];
        // To store lowercase character
        if (chr >= 'a' && chr <= 'z') {
            v[chr - 'a']++;
        }
        // To store uppercase character
        else if (chr >= 'A' && chr <= 'Z') {
            v[chr - 'A']++;
        }
    }
    // Sort the vector
    sort(v.begin(), v.end());
    // Intialise answer variable
    int ans = 0;
    // Get the answer in accordance with the frequencies and range [1, 26]
    for (int i = 25; i >= 0; i--) {
        // Check if the value of frequency is 0 or not, if 0 then stop the loop
        if (v[i] == 0) {
            break;
        }
        else{
            // Add the highest frequency with a number that is initially set to 26
            ans+=v[i] * (i + 1);
        }
    }
    // Return the maximum sum obtained
    return ans;
}
int main(){
   // Give the input string
   string S = "aBAbgha";
   // Call the helper function to maximize the String value by assigning values in the range [1, 26] to each character
   cout << "The maximum string value by assigning values in the range [1, 26] to each character is: "<<Helper(S);
   return 0;
}

输出

The maximum string value by assigning values in the range [1, 26] to each character is: 175

上面的代码的复杂性

• 时间复杂性−O(n*(log(n)))；我们使用循环，但它们将运行‘n’次，然而，排序函数将花费（n * log(n)）的时间执行，因此我们将代码的总体复杂性定义为n * log(n)。

• 空间复杂性−O(26)；因为英语语言中只有26个不同的字母存在。

注意−上述方法使用频率向量而不是在映射中存储频率。

结论

在本文中，为了最大化字符串值，我们采用了两种方法来存储每个元素的频率。在第一种方法中，我们使用映射来存储每个字母的频率，无论字母是大小写。然而，在第二种方法中，我们可以避免映射占用的额外空间，并直接使用频率向量。