在这个问题中，我们需要对每个字符串前缀执行给定的操作。最后，我们需要统计每个字符的频率。

我们可以采用贪心算法来解决这个问题。我们需要取长度为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的前缀执行上述操作 <= K <= N。执行完上述操作后，我们需要打印每个字符的出现频率。

示例示例

输入

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 步- 打印字符的频率。

示例

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

void performOperations(string &str, vector<int> &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<int> 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来存储字符频率，而不是使用列表。对于更多练习，程序员可以尝试打印更新后字符串中每个字符的累积频率。