C++ 当重新定义了一些ASCII值时，求最大ASCII和的子字符串

在这个问题中，我们将找到给定字符串的子字符串，其字符的ASCII值之和在重新定义ASCII值时是最大的。

解决这个问题的一种朴素方法是找到所有子字符串的字符的ASCII值之和，并得到具有最大和的子字符串。

解决问题的另一种方法是使用Kadane算法找到最大子数组和。

问题陈述 - 我们给定了一个大小为N的字符串alpha，其中包含字母字符。我们还给出了大小为M的chars[]和ASCII[]数组，其中chars[]包含字符，Ascii[i]包含chars[i]字符的更新后的ASCII值。此外，请注意字符串是区分大小写的。

我们需要找到字符的ASCII值之和最大的子字符串。

示例示例

输入

alpha = "apper"; chars[char_len] = {'p'}; Ascii[char_len] = {-800};

输出结果

'er'

说明 - 这里，’p’的ASCII值是-800。所以，’er’的ASCII值之和是最大的。

输入

alpha = "accebd"; chars[char_len] = {'b'}; Ascii[char_len] = {-500};

输出

'acce'

解释 - 这里，我们不能将“b”包含在子字符串中，因为它的ASCII值为负数，这会减少字符串字符的ASCII值的总和。

输入

alpha = "ababc"; chars[char_len] = {'a', 'b', 'c'}; Ascii[char_len] = {100, -100, 200};

输出

'ababc'

说明 - 我们可以将一个字符串作为子字符串，因为它具有字符ASCII值的最大和。

方法1

在这个方法中，我们将找出给定字符串的所有子字符串。然后，我们将对所有字符的ASCII值求和。如果我们已经给出了特定字符的更新ASCII值，我们将使用更新后的ASCII值。否则，我们将使用原始ASCII值。

同时，我们将跟踪ASCII值总和最大的子字符串。

算法

步骤1 - 初始化’temp’和’result’字符串，分别用于存储临时子字符串和结果字符串。

步骤2 - 如果字符串长度为’1’，返回该字符串本身。

步骤3 - 将’maxVal’变量初始化为最小值，用于存储最大和，将’sum’初始化为0，用于存储子字符串字符的ASCII值之和。还要定义一个map，用于存储字符的更新频率。

步骤4 - 将所有具有更新后的ASCII值的字符添加到map中。

步骤5 - 开始遍历字符串。还要使用另一个嵌套循环从p索引到q索引获取子字符串。

步骤6 - 在嵌套循环中，使用substr()方法从p索引开始获取长度为q-p+1的子字符串。将其存储在’temp’字符串中，并将’sum’变量重新初始化为0。

步骤7 - 遍历temp字符串以获取其字符的ASCII值之和。如果当前字符存在于map中，则将其值添加到sum中。否则，将当前字符的原始ASCII值添加到sum中。

步骤8 - 如果sum大于’maxVal’，使用sum更新’maxVal’，并使用’temp’更新’result’。

步骤9 - 返回结果值。

示例

#include <bits/stdc++.h>
using namespace std;

string getMaximumSum(string alpha, char chars[], int Ascii[], int chars_len) {
   string temp = "", result = "";
   // For string of size 1
   if (alpha.length() == 1)
     return alpha;
   long long maxVal = INT_MIN, sum = 0;
   unordered_map<char, int> charMap;
   // Storing new ASCII values to map
   for (int p = 0; p < chars_len; p++) {
     charMap[chars[p]] = Ascii[p];
   }
   // Get all substrings and sum its characters ASCII values
   for (int p = 0; p < alpha.length(); p++) {
     for (int q = p; q < alpha.length(); q++) {
       // Get substring
       temp = alpha.substr(p, q - p + 1);
       sum = 0;
       // Traverse substring to count the sum of ASCII values
       for (int r = 0; r < temp.length(); r++) {
         // If Character exists in the map
         if (charMap.find(temp[r]) != charMap.end()) {
            sum += charMap[temp[r]];
         } else {
            // If the character doesn't exist in the map
            sum += temp[r];
         }
       }
       // Update maximum value if the sum is greater
       if (sum > maxVal) {
         maxVal = sum;
         result = temp;
       }
     }
   }
   return result;
}

int main() {
   string alpha = "apper";
   int char_len = 1;
   char chars[char_len] = {'p'};
   int Ascii[char_len] = {-800};
   cout << "The maximum sum of ASCII values of any substring of the given string is " << getMaximumSum(alpha, chars, Ascii, char_len) << endl;
   return 0;
}

结果

The maximum sum of ASCII values of any substring of the given string is er

时间复杂度 – O(NNN) 获取所有子串。

空间复杂度 – O(N + M)，将子串存储在’temp’字符串中，将更新的ASCII值存储在映射中。

方法2

使用Kadane算法找到子数组的最大和，在这里，我们可以将字符串视为字符数组，并找到ASCII值总和最大的子串。

在Kadane算法中，当总和变为负数时，我们将其重新初始化为0，并从一个新的子串开始。

算法

第1步 - 如果字符串长度为1，则返回字符串。

第2步 - 将更新的ASCII值存储在映射中。

第3步 - 开始遍历字符串，并将当前字符附加到’temp’字符串中。

第4步 - 如果当前字符存在于映射中，则将其值添加到总和中。否则，将字符的原始ASCII值添加到总和中。

第5步 - 如果总和为负数，则将总和重新初始化为0，并清除’temp’字符串。

第6步 - 如果总和大于’maxVal’，则用总和更新’maxVal’，并用’temp’字符串更新’result’。

第7步 - 返回结果字符串。

示例

#include <bits/stdc++.h>
using namespace std;

string getMaximumSum(string alpha, char chars[], int Ascii[], int chars_len) {
   string temp = "", result = "";
   // For string of size 1
   if (alpha.length() == 1)
     return alpha;
   long long maxVal = INT_MIN, sum = 0;
   unordered_map<char, int> charMap;
   // Storing new ASCII values to map
   for (int p = 0; p < chars_len; p++) {
     charMap[chars[p]] = Ascii[p];
   }
   // Iterate the string
   for (int p = 0; p < alpha.length(); p++) {
     // Store the string in temp.
     temp += alpha[p];
     // To get updated ASCII value
     if (charMap.find(alpha[p]) == charMap.end()) {
       sum += alpha[p];
     } else {
       sum += charMap[alpha[p]];
     }
     // For negative sum, we make it 0 and clear the string
     if (sum < 0) {
       sum = 0;
       temp.clear();
     }
     // When the sum is greater than maxVal, update it.
     if (sum > maxVal) {
       maxVal = sum;
       result = temp;
     }
   }
   return result;
}
int main() {
   string alpha = "accebd";
   int char_len = 1;
   char chars[char_len] = {'b'};
   int Ascii[char_len] = {-500};
   cout << "The maximum sum of ASCII values of any substring of the given string is " << getMaximumSum(alpha, chars, Ascii, char_len) << endl;
   return 0;
}

输出

The maximum sum of ASCII values of any substring of the given string is acce

时间复杂度 – O(N) 遍历字符串。

空间复杂度 – O(N) 存储子字符串。

当我们需要获取具有最大和的子数组时，Kadane算法非常有用，因为我们可以在O(N)时间内得到答案。朴素的方法需要O(N^2)的时间。