在这个问题中，我们需要对每个字符串前缀执行给定的操作。最后，我们需要统计每个字符的频率。
我们可以采用贪心算法来解决这个问题。我们需要取长度为K的每个前缀，并根据给定的条件更新其字符。我们可以使用map来计算最终字符串中字符的频率。
问题陈述 - 我们给出了包含 N 个小写字母字符的字符串 tr。另外，我们还给出了映射列表，总共包含 26 个元素。每个元素根据其值映射到小写字符。例如，mapping[0] 映射到“a”，mapping[1] 映射到“b”，mapping[25] 映射到“z”。此外，映射数组包含 1 或 -1。
我们需要执行以下操作。
从长度为K的前缀中获取最大字符，并从'mapping'数组中获取映射值。
如果映射值为1，则将所有前缀元素增加1。
如果映射的值为-1，则将所有前缀元素减1。
在这里，增加元素意味着 ‘a’ −> ‘b’，‘b’ −> ‘c’，… ‘z’ −> ‘a’。
递减的元素意味着，‘a’->‘z’，‘b’->‘a’，…。 ‘z’->‘y’。
我们需要对每个长度为1的前缀执行上述操作
示例示例
输入
mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = ‘progress’
输出
0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0
说明
在长度为1的前缀中，最大的字符是 'p'，映射为 -1。因此，更新后的字符串将是 'orogress'。
长度为2的前缀中，最大字符为‘r’，映射为-1。因此，更新后的字符串将是“nqogress”。
在长度为3的前缀中，最大的字符是‘q’，映射值为1。因此，更新后的字符串为‘orpgress’。
当我们完成所有操作后，最终的字符串将是'pqmfpdqr'，其中包含1个'f'，2个'p'，2个'q'，1个'm'，1个'd'和1个'd' 'r'。在输出中，我们打印了结果字符串中每个字符的频率。
输入
mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = "ab",
输出
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
解释− 在执行所有操作之后，最终的字符串是'ac'，我们打印了每个字符的频率。
方法一
在这种方法中，我们将遍历字符串并取K的值等于索引P。之后，我们将取长度等于P的前缀，找到最大字符，取映射值，并相应地更新所有前缀字符。
算法
步骤 1 − 定义‘max_char’变量来存储给定前缀的最大字符。
步骤2 − 同样地，用零初始化长度为26的列表，以便存储最终字符串中每个字符的频率。
第 3 步- 开始遍历字符串，并在循环内用 96 初始化“max_char”变量。
第 4 步- 使用嵌套循环从长度为 p 的前缀中查找最大字符。
步骤 5 - 通过添加 max_char 的映射值来更新前缀的每个字符。
第 7 步- 如果更新的字符小于“a”，则将其更新为“z”。
第 8 步- 如果更新的字符大于“z”，则将其更新为“a”。
第9步− 最后，通过遍历更新后的字符串，将每个字符的频率存储在列表中。
第 10 步- 打印字符的频率。
示例
#includeusing namespace std; void performOperations(string &str, vector &mapping) { int len = str.length(); char max_char; // array to store the final frequency of each character int freq[26] = {0}; for (int p = 0; p < len; p++) { max_char = 96; // Get the maximum character from the prefix string for (int q = 0; q <= p; q++) { max_char = max(max_char, str[q]); } // Update the prefix string by adding the max character's value. for (int q = 0; q <= p; q++) { // adding the mapping value to the current character str[q] += mapping[max_char - 'a']; // If the updated value is greater than z or less than a, update it if (str[q] < 'a') { str[q] = 'z'; } else if (str[q] > 'z') { str[q] = 'a'; } } } // Counting frequency of each character for (int p = 0; p < len; p++) { freq[str[p] - 'a']++; } // print count of each character in the updated string for (auto ch : freq) { cout << ch << ' '; } } int main() { string S = "progress"; vector mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}; performOperations(S, mapping); return 0; }
输出
0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0
时间复杂度− O(N*N)因为我们使用两个嵌套循环遍历字符串。
空间复杂度− O(1)，因为我们使用恒定空间来存储字符的频率。
结论
我们对输入字符串执行了给定的操作，并在输出中打印了更新后字符串的字符频率。程序员还可以使用C++中的map来存储字符频率，而不是使用列表。对于更多练习，程序员可以尝试打印更新后字符串中每个字符的累积频率。
