使字串中所有字元相同所需替換的最小字元數

---

在這個問題中，我們將找到使所有字元都相同所需的最小字串字元數。在第一種方法中，我們將透過計算給定字串中每個字元的頻率來找到可替換字元的最小計數。在另一種方法中，我們將確定將所有字串字元轉換為特定字元的成本，並從中取最小值。

問題陳述 – 我們得到了一個包含 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)，因為我們不使用任何額外空間。

我們學習了兩種使用相同邏輯解決問題的方法。當我們將字串的所有字元都設定為頻率最大的特定字元時，我們需要進行最少的替換。