C++ 将给定字符串中的字符替换为相同字符所需的最小字符数

在这个问题中，我们将找到一个最小的字符数，需替换所有字符以使它们相同。在第一种方法中，我们将通过计算给定字符串中每个字符的频率来找到可替换字符的最小计数。在另一种方法中，我们将确定将所有字符串字符转换为一个特定字符的成本，并从中取最小值。

问题陈述 - 给定一个包含N个字母字符的字符串alpha，我们需要找到最小的字符数，以使所有字符串字符相等。

示例

输入

alpha = "abca"

输出

2

解释 – 我们可以用 ‘a’ 替换 ‘b’ 和 ‘c’ 以使所有字符相等。

输入

alpha = ‘aaaa’

输出

0

Explanation – 我们需要替换0个字符，因为字符串的所有字符都相等。

Input

alpha = ‘abcde’

输出结果

4

解释 - 我们需要替换字符串中的任意4个字符，因为字符串中的所有字符都是不同的。

方法1

在这个方法中，我们将使用map数据结构来存储给定字符串中每个字符的频率。然后，我们将找到最大频率，并通过从字符串长度中减去该频率来得到答案。

算法

Step 1 - 定义一个名为”map”的charMap，将字符映射到一个整数。

Step 2 - 遍历字符串，并在map中更新字符频率。

Step 3 - 用0初始化maxFreq变量。

Step 4 - 进行26次迭代，从0开始获取字符串中每个字符的频率。将最大频率存储在maxFreq变量中。

Step 5 - 将maxFreq的值从字符串长度中减去后，返回答案。

示例

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

int getReplacableChars(string alpha){
    // Map to store char frequency
    map<char, int> charMap;
    // store char frequency in the map
    for (int p = 0; p < alpha.size(); p++) {
        charMap[alpha[p]]++;
    }
    // Find the maximum frequency
    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 << "Minimum characters we need to replace in the given string to make all characters the same is " << getReplacableChars(alpha);
    return 0;
}

输出

Minimum characters we need to replace in the given string to make all characters the same is 2

时间复杂度 – O(N)：计算字符串中字符的频率。

空间复杂度 – O(26)：存储每个字符的频率。

方法二

在这种方法中，我们将计算需要替换的字符，使得所有字符都等于特定的字符。我们将为每个字母字符计算这样的成本，并从中选择最小成本。

算法

第1步： 用最大整数值初始化’repCost’变量。

第2步： 从’a’到’z’遍历所有字母字符。

第3步： 用0将’charCost’变量初始化，以存储使字符串的所有字符等于’ch’字符所需的替换次数。

第4步： 遍历字符串，如果字符串的任何字符不等于’ch’，则将’charCost’的值增加1。

第5步： 将’repCost’的值更新为’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++) {
        // To store the cost of making all characters equal to ch
        int charCost = 0;
        for (int p = 0; p < alpha.size(); p++) {
            // Increase cost if character mismatch
            if (alpha[p] != ch) {
                charCost++;
            }
        }
        // Store minimum cost
        repCost = min(repCost, charCost);
    }
    // Return cost
    return repCost;
}
int main() {
    string alpha = "abca";
    cout << "Minimum characters we need to replace in the given string to make all characters the same is " << getReplacableChars(alpha);
    return 0;
}

输出

Minimum characters we need to replace in the given string to make all characters the same is 2

时间复杂度 – O(N)，遍历字符串。

空间复杂度 – O(1)，因为我们不使用任何额外的空间。

我们学习了两种使用相同逻辑解决问题的方法。当我们将字符串的所有字符都变为频率最高的特定字符时，我们需要进行最小替换。