使给定字符串中的所有字符相同，需要替换的最少字符数
在本题中，我们将求出使所有字符相同，需要替换的最少字符串字符数。在第一种方法中，我们将通过计算给定字符串中每个字符的频率来找到可替换字符的最小数量。在另一种方法中，我们将确定将所有字符串字符转换为特定字符的成本，并从中取最小值。
问题描述 – 我们给定一个包含 N 个字母字符的字符串 alpha。我们需要找到最少需要替换的字符数，以使所有字符串字符相等。
示例
输入
alpha = "abca"
输出
2
解释 – 我们可以将"b"和"c"替换为"a"，以使所有字符相等。
输入
alpha = 'aaaa'
输出
0
解释– 由于字符串中的所有字符都相同，因此我们需要替换 0 个字符。
输入
alpha = 'abcde'
输出
4
解释 – 由于字符串中的所有字符都不同，因此我们需要替换字符串中的任意 4 个字符。
方法 1
在此方法中，我们将使用 map 数据结构来存储给定字符串中每个字符的频率。之后，我们将找到最大频率，并通过从字符串长度中减去该频率来获取答案。
算法
步骤 1 – 定义名为"map"的"charMap"，将字符映射到整数。
步骤 2 – 遍历字符串并更新映射中的字符频率。
步骤 3 – 将"maxFreq"变量初始化为 0。
步骤 4 – 从 0 开始，共进行 26 次迭代，以获取字符串中每个字符的频率。在"maxFreq"变量中，存储任意字符的最大频率。
步骤 5 – 从字符串长度中减去 maxFreq 值后返回答案。
示例
#include <bits/stdc++.h>
using namespace std;
int getReplacableChars(string alpha){
// 映射以存储字符频率
map<char, int> charMap;
// 将字符频率存储在映射中
for (int p = 0; p < alpha.size(); p++) {
charMap[alpha[p]]++;
}
// 找到最大频率
int maxFreq = 0;
for (int p = 0; p < 26; p++) {
maxFreq = max(maxFreq, charMap['a' + p]);
}
return alpha.size() - maxFreq;
}
int main() {
string alpha = "abca";
cout << "为了使给定字符串中的所有字符相同，我们需要替换的最少字符数是 " << getReplacableChars(alpha);
return 0;
}
输出
为了使给定字符串中的所有字符相同，我们需要替换的最少字符数是 2
时间复杂度 – 计算字符串中字符的频率，复杂度为 O(N)。
空间复杂度 – 存储每个字符的频率，复杂度为 O(26)。
方法 2
在此方法中，我们将计算需要替换的字符数，以使所有字符都等于特定字符。我们将计算每个字母字符的替换成本，并从中取出最低成本。
算法
步骤 1 – 使用最大整数值初始化 'repCost' 变量。
步骤 2 – 遍历从 'a' 到 'z' 的所有字母字符。
步骤 3 – 使用 0 初始化 'charCost' 变量，用于存储使字符串所有字符等于 'ch' 字符所需的替换总数。
步骤 4 – 遍历字符串，如果字符串中有任何字符不等于 'ch'，则将 'charCost' 的值加 1。
步骤 5 – 使用 'repCost' 和 'ch' 之间的最小值更新 'repCost' 变量的值。 'charCost'。
步骤 6 – 返回 'repCost' 值。
示例
#include <bits/stdc++.h>
using namespace std;
int getReplacableChars(string alpha) {
int repCost = INT_MAX;
for (char ch = 'a'; ch <= 'z'; ch++) {
// 存储使所有字符等于 ch 的成本
int charCost = 0;
for (int p = 0; p < alpha.size(); p++) {
// 如果字符不匹配则增加成本
if (alpha[p] != ch) {
charCost++;
}
}
// 存储最低成本
repCost = min(repCost, charCost);
}
// 返回成本
return repCost;
}
int main() {
string alpha = "abca";
cout << "为了使给定字符串中的所有字符相同，我们需要替换的最少字符数是 " << getReplacableChars(alpha);
return 0;
}
输出
为了使给定字符串中的所有字符相同，我们需要替换的最少字符数是 2
时间复杂度 – 遍历字符串的复杂度为 O(N)。
空间复杂度 – O(1)，因为我们不使用任何额外空间。
我们学习了两种使用相同逻辑解决问题的方法。当我们使字符串中的所有字符都等于出现频率最高的特定字符时，我们需要进行最少的替换。
