C++ 长度最小的子字符串要替换以使每个字符的频率为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变量。同时，初始化minLen变量为len + 1，假设子串的长度等于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)，因为我们使用恒定的空间在哈希映射中存储字符频率。

程序员应确保输入字符串包含最多不同字符。我们使用了映射数据结构来存储额外的字符，并基于此，我们决定了滑动窗口的最小长度。