資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究替換最小子字串長度，使每個字元的頻率為N/3
在這個問題中，我們需要找到最小的子字串，以便我們可以替換其字元，並使給定字串中每個字元的頻率等於 N/3。
我們可以使用滑動視窗技術來解決這個問題。我們可以找到包含所有多餘字元的最小視窗大小，這將是問題的答案。
問題陳述 – 我們得到一個字串 alpha。alpha 的大小為 N，它總是能被 3 整除。給定的任務是找到最小長度的子字串，以便我們可以替換其任何字元，並確保字串中每個字元的出現次數正好為 N/3。
注意 – 字串最多包含三個不同的字元。
示例
輸入
alpha = ‘NMM’
輸出
1
解釋 – 最小的子字串是 ‘N’，我們需要更改它才能使字串中所有字元的頻率等於 N/3。
輸入
alpha = "BEGBBG";
輸出
1
解釋 – 最小的子字串是 ‘E’，我們需要將其更改為 ‘BGGBBG’，使其包含所有頻率等於 N/3 的字元。
輸入
alpha = ‘DDDQQQ’
輸出
2
解釋 – 最小的子字串是 ‘DQ’，我們需要用任何字元替換它，才能使所有字元的頻率等於 N/3。
方法 1
在這種方法中，我們將首先找到字元頻率。根據字元頻率，我們將確定多餘的字元。之後，我們將找到包含所有多餘字元的最小視窗長度，我們可以取相同長度的子字串顯示在輸出中。
演算法
步驟 1 – 如果字串長度為零，則返回 0，因為我們需要長度為 0 的子字串。
步驟 2 – 定義 charFreq 雜湊對映來儲存所有字元的頻率。遍歷字串並將每個字元的頻率儲存在對映中。
步驟 3 – 定義 excessChars 對映來儲存多餘字元的頻率。
步驟 4 – 遍歷 charFreq 對映。如果任何鍵的值大於 len/3，則將該鍵新增到 excessChars 對映中，其值為其頻率 – len/3。
步驟 5 – 如果 excessChars 的大小為零，則表示沒有多餘的字元。因此，返回 0。
步驟 6 – 為滑動視窗初始化 p 和 q 變數。還使用 len + 1 初始化 minLen 變數，假設子字串的長度等於 len + 1。
步驟 7 – 在 ‘cnt’ 變數中，儲存 excessChars 對映的大小。此外，使用 while 迴圈遍歷字串。
步驟 8 – 如果當前字元存在於 excessChars 對映中，則將其值減 1，因為我們將其包含在當前視窗中。
步驟 9 – 如果 excessChars[c] 的值為零，則將 ‘cnt’ 值減 1，因為當前視窗包含字元 c 的所有額外出現。
步驟 10 – 如果 ‘cnt’ 等於零，則當前視窗包含所有額外字元的出現。因此，我們需要開始減小視窗大小以獲得最小視窗大小。
步驟 11 – 遍歷字串，直到 p < len && cnt == 0 條件變為 false。
步驟 11.1 – 在 minLen 變數中，儲存 minLen 和 q – p + 1 的最小值，即當前視窗大小。
步驟 11.2 – 如果當前字元存在於 excessChars 雜湊對映中，則將其值加 1，如果 excessChars[alpha[p]] == 1 為真，則將 ‘cnt’ 的值加 1。
步驟 11.3 – 增加 q 和 p 值。
步驟 12 – 返回 ‘minLen’ 變數值。
示例
#include <bits/stdc++.h>
using namespace std;
int countSize(string alpha) {
int len = alpha.length();
// return 0 if the string is empty
if (len == 0) {
return 0;
}
// to store character frequency
map<char, int> charFreq;
// calculate the frequency of each character
for (char c : alpha) {
charFreq[c]++;
}
// Count of extra characters
map<char, int> excessChars;
// Calculating excess characters
for (auto c : charFreq) {
if (c.second > len / 3) {
excessChars[c.first] = (c.second - len / 3);
}
}
// If no extra character is present in the string, return 0 as the string is balanced.
if (excessChars.size() == 0) {
return 0;
}
// sliding window
int p = 0, q = 0;
// Need to find minimum window length
int minLen = len + 1;
// total extra characters
int cnt = excessChars.size();
while (q < len) {
// character at q index
char c = alpha[q];
// If c is extra
if (excessChars.find(c) != excessChars.end()) {
// Decrease frequency of c in the current window
excessChars[c]--;
// If all extra chars are consumed, decrease the number of extra chars by 1
if (excessChars[c] == 0) {
cnt--;
}
}
// If the window contains all extra characters
if (cnt == 0) {
// Start decreasing window size
while (p < len && cnt == 0) {
// Get minimum window length
minLen = min(minLen, q - p + 1);
// If we find extra character
if (excessChars.find(alpha[p]) != excessChars.end()) {
// Change char frequency in the current window
excessChars[alpha[p]]++;
// Add 1 in extra chars count
if (excessChars[alpha[p]] == 1) {
cnt++;
}
}
p++;
}
}
q++;
}
return minLen;
}
int main() {
string alpha = "BEGBBG";
cout << "The size of the smallest substring to replace characters is - " << countSize(alpha);
return 0;
}
輸出
The size of the smallest substring to replace characters is - 1
時間複雜度 – O(N)，因為我們遍歷字串並使用滑動視窗技術。
空間複雜度 – O(1)，因為我們使用常量空間來在雜湊對映中儲存字元頻率。
程式設計師應該確保輸入字串最多包含不同的字元。我們使用 map 資料結構來儲存多餘的字元，並據此確定滑動視窗的最小長度。
102 次瀏覽
