C++ 每个前缀的长度在执行描述的操作后小写字符的计数

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

我们可以采用贪心的方法来解决这个问题。我们需要取长度为K的每个前缀，并根据给定的条件更新其字符。我们可以用映射来计算最终字符串中字符的频率。

问题陈述 - 我们给出了包含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到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个‘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’，并且我们打印了每个字符的频率。

方法1

在这个方法中，我们将遍历字符串，并将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来存储字符频率，而不是使用列表。对于更多练习，程序员可以尝试打印更新后字符串中每个字符的累计频率。