在这个问题中，我们需要对每个字符串前缀执行给定的操作。最后，我们需要统计每个字符的频率。
我们可以采用贪心算法来解决这个问题。我们需要取长度为K的每个前缀，并根据给定的条件更新其字符。我们可以使用map来计算最终字符串中字符的频率。
问题陈述 - 我们给出了包含 N 个小写字母字符的字符串 tr。另外，我们还给出了映射列表，总共包含 26 个元素。每个元素根据其值映射到小写字符。例如，mapping[0] 映射到“a”，mapping[1] 映射到“b”，mapping[25] 映射到“z”。此外，映射数组包含 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)因为我们使用两个嵌套
.........................................................