使字符串中所有字符相同所需替换的最小字符数

---

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

问题陈述 – 我们得到了一个包含 N 个字母字符的字符串 alpha。我们需要找到使所有字符串字符相等的最小字符替换数。

示例

输入

alpha = "abca"

输出

2

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

输入

alpha = ‘aaaa’

输出

0

解释 – 我们不需要替换任何字符，因为字符串的所有字符都相等。

输入

alpha = ‘abcde’

输出

4

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

方法 1

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

算法

步骤 1 – 定义名为 ‘charMap’ 的 ‘map’ 来将字符映射到整数。

步骤 2 – 遍历字符串并在 map 中更新字符频率。

步骤 3 – 将 ‘maxFreq’ 变量初始化为 0。

步骤 4 – 从 0 开始进行总共 26 次迭代，以获取字符串中每个字符的频率。在 ‘maxFreq’ 变量中，存储任何字符的最大频率。

步骤 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)，用于存储每个字符的频率。

方法 2

在这种方法中，我们将计算使所有字符等于特定字符所需的字符替换数。我们将为每个字母字符计算此类成本，并从中取最小成本。

算法

步骤 1 – 将 ‘repCost’ 变量初始化为最大整数值。

步骤 2 – 遍历从 ‘a’ 到 ‘z’ 的所有字母字符。

步骤 3 – 将 ‘charCost’ 变量初始化为 0，以存储使字符串的所有字符等于 ‘ch’ 字符所需的总替换次数。

步骤 4 – 遍历字符串，如果字符串的任何字符都不等于 ‘ch’，则将 ‘charCost’ 的值加 1。

步骤 5 – 使用 ‘repCost’ 和 ‘charCost’ 之间的最小值更新 ‘repCost’ 变量的值。

步骤 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)，因为我们不使用任何额外空间。

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