在给定约束条件下，查找 N 次操作后的值以删除字符串"S"中的 N 个字符
使用字符串的规范是什么?
解决涉及给定字符串 S 的特定挑战。字符串 S 仅包含小写英文字母，删除字符时必须遵循某些约束。
给定的约束是 −
字符串 S 中有小写英文字母。
只有当字符在字符串中出现多次时才能删除它。
只有连续出现的字符才能被删除。以下步骤可用于从字符串 S 中删除字符 -
在迭代字符串 S 时，查找所有出现超过一次的字符。通过对每个字符再次迭代字符串 S，查找字符的所有连续出现。
如果连续出现的次数大于或等于迭代次数，则删除字符的前 N 次出现。
继续执行步骤 2 和 3，直到所有迭代完成。
最后，通过返回最终字符串 S，可以发现在删除 N 个字符的 N 次操作之后字符串的值。
语法
本主题是一个编码问题，涉及通过对给定字符串执行一定数量的操作来对其进行操作。在每个操作中，删除字符串中最常见的字符，并更新每个剩余字符的频率。执行 N 次操作后，通过对每个剩余字符的频率求平方并相加来计算字符串的最终值。问题的目标是编写一个程序，以字符串和数字 N 作为输入，并根据给定的约束执行 N 次操作后输出字符串的最终值。
以下是函数的语法，该函数在给定约束的情况下，在 N 次操作后找到值以删除字符串 S 中的 N 个字符 -
int findvalueafterNoperations(int n, string s) {
int len = s.length();
int freq[26] = {0};
for (int i = 0; i < len; i++) {
freq[s[i] - 'a']++;
}
sort(freq, freq + 26, greater<int>());
for (int i = 0; i < n; i++) {
freq[0]--;
sort(freq, freq + 26, greater<int>());
}
int value = 0;
for (int i = 0; i < 26; i++) {
value += freq[i] * freq[i];
}
return value;
}
此函数接受两个参数 -
n - 表示要执行的操作数的整数。
s - 表示输入字符串的字符串。
该函数首先使用数组计算输入字符串中每个字符的频率。然后按降序对该频率数组进行排序并执行 N 次操作，其中每次操作都会减少最常见字符的频率并再次对频率数组进行排序。
最后，函数通过对排序后的频率数组中每个字符的频率平方求和来计算字符串的值并将其作为整数返回。
算法
经过 N 次字符删除过程后，该算法在以下限制下计算字符串的值。输入由数字 N 和字符串 S 组成。
步骤 1 - 使用数组确定输入字符串中每个字符的频率。
步骤 2 - 按降序排列此频率数组。
步骤 3 - 执行 N 次操作，每次操作都会降低频率数组中出现频率最高的字符的频率。
步骤 4 - 重新排列频率数组。
步骤 5 - 将排序后的频率数组中每个字符的频率平方相加，以确定字符串的值。
步骤 6 - 经过 N 次操作后，字符串的值是其平方。
此技术有效，因为问题要求从输入字符串 S 中删除 N 个字符，这就像执行 N 个操作，其中每个操作都会删除一次字符串中最频繁的字符。由于任务的限制，我们无法真正从字符串中删除字符，因此我们必须通过在每个操作中降低频率数组中最常见字符的频率来模拟此操作。
要遵循的方法
方法 1
使用代码初始化示例字符串 S 和各种操作 N。然后在循环每个操作后删除大于其下一个字符的初始字符。如果没有删除，则消除最后一个字符。在完成所有操作后，它会打印字符串的最终值。
在这里，代码假设 N 短于或等于字符串 S 的长度。如果 N 长于 S，则代码将无法按预期运行。
示例 1
#include <iostream>
#include <string>
using namespace std;
int main(){
string S = "abcdefg";
int N = 3;
for (int l = 1; l <= N; l++) {
int p=0;
while(p<S.length()- 1) {
if(S[p]>S[p+1]) {
S.erase(p, 1);
break;
}
p++;
}
if(p==S.length()- 1) {
S.erase(p, 1);
}
}
cout<< S << endl;
return 0 ;
}
输出
a b c d
方法 2
在此代码中，首先使用数组确定输入字符串中每个字符的频率。接下来，我们执行 N 次操作，每次操作中减少最常见字符的频率，并再次对频率数组进行排序。接下来，我们按降序对这个频率数组进行排序。
最终通过将排序后的频率数组中每个字符的频率平方相加来确定字符串的值。
示例 2
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
// Given values
int n = 3;
string s = "abcabc";
int len = s.length();
int freq[26] = {0};
for (int i = 0; i < len; i++) {
freq[s[i] - 'a']++;
}
sort(freq, freq + 26, greater<int>());
for (int i = 0; i < n; i++) {
freq[0]--;
sort(freq, freq + 26, greater<int>());
}
int value = 0;
for (int i = 0; i < 26; i++) {
value += freq[i] * freq[i];
}
cout << "Value of string after " << n << " operations: " << value << endl;
return 0;
}
输出
Value of string after 3 operations: 3
结论
总之，我们可以使用直接技术在 N 次操作后获得值，从而在上述限制下从字符串"S"中消除 N 个字符。首先，让我们初始化频率数组以跟踪字符串中有多少个字符。一旦我们消除了 N 个字符，我们就可以重复从频率数组中删除计数最大的字符的过程。此过程总共可重复 N 次。
借助这种方法，我们可以在 N 次操作(包括消除 N 个字符)后快速确定字符串"S"的值。由于该方法中的排序阶段，此解决方案的时间复杂度为 O(N logN)，这对于大多数实际应用来说是可以接受的。
