数据结构
网络
关系数据库管理系统 (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 次浏览
