子串中字符相同且频率差最多为K的最长子序列

---

在这个问题中，我们将找到子序列的最大长度，该子序列应包含连续的字符，并且所有字符的频率差不会超过K。

我们需要找到给定字符串的所有可能的子序列，并检查它是否包含每个字符连续且最大频率差以获得输出。

问题陈述 - 我们得到一个包含小写字母字符的字符串alpha。我们还得到了正整数K。我们需要找到给定字符串子序列的最大长度，该子序列遵循以下规则。

• 特定字符的所有出现都应该是连续的。

• 字符的频率差不得超过K。

示例

输入

alpha = "ppppqrs", K = 2

输出

6

解释 - 我们可以取子序列'pppqrs'。最大字符频率为3，最小字符频率为1。因此，差异为2。此外，它包含所有连续的字符。

输入

alpha = "abbbbc", K = 2

输出

5

解释 - 我们可以取子序列'abbbc'。

输入

alpha = "mnnnnnnno", k = 3;

输出

7

解释 - 我们可以取子序列'nnnnnnn'。

方法1

在这种方法中，我们将使用递归函数来查找给定长度的所有子序列。此外，我们将定义一个函数来检查子序列是否包含所有连续的字符。我们将使用map数据结构来计算最大和最小频率差。

算法

步骤1 - 定义'f'映射以存储字符的频率。

步骤2 - 如果start等于临时字符串的长度，并且字符串长度大于0，则执行以下步骤。

步骤3 - 初始化'minf'和'maxf'变量以存储最小和最大频率。

步骤4 - 清空映射，并将每个字符的频率存储在映射中。

步骤5 - 遍历映射值并找到最大和最小频率值。

步骤6 - 如果最大和最小频率差小于或等于K，则检查字符串是否包含连续字符。

步骤6.1 - 在checkForContinuous()函数中，定义'pos'映射以存储特定字符的最后一个位置。

步骤6.2 - 遍历字符串。如果映射中存在当前字符，并且当前位置和字符的最后一个位置之间的差小于1，则更新最后一个位置。否则，返回false。

步骤6.3 - 如果字符不存在，则将字符添加到映射中。

步骤6.4 - 最后返回true。

步骤7 - 如果字符串包含连续字符，并且频率差小于K，则如果'maxi'小于当前子序列的长度，则更新'maxi'的值。

步骤8 - 排除当前字符后进行递归调用。

步骤9 - 将当前字符追加到临时字符串的末尾。此外，使用更新的'tmp'字符串进行递归调用。

示例

#include <bits/stdc++.h>
using namespace std;

int maxi = 0;
// Check for continuous characters in the substring
bool CheckForContinuous(string &tmp) {
    // map to store the last index of the character
    unordered_map<char, int> pos;
    for (int p = 0; p < tmp.length(); p++) {
        // When the last index exists in the map
        if (pos[tmp[p]]) {
            // If the last index is adjacent to the current index
            if (p - pos[tmp[p]] + 1 <= 1)
                pos[tmp[p]] = p + 1;
            else
                return false;
        } else {
            // When the map doesn't have a character as a key
            pos[tmp[p]] = p + 1;
        }
    }
    return true;
}
void getLongestSubSeq(string &alpha, string tmp, int start, int &k) {
    // To store the character's frequency
    unordered_map<char, int> f;
    if (start == alpha.length()) {
        if (tmp.length() > 0) {
            // To store minimum and maximum frequency of characters
            int minf = INT_MAX, maxf = INT_MIN;
            // Make map empty
            f.clear();
            // Store frequency of characters in the map
            for (int p = 0; p < tmp.length(); p++)
                f[tmp[p]]++;

            // Get minimum and maximum value from the map
            for (auto &key : f) {
                minf = min(minf, key.second);
                maxf = max(maxf, key.second);
            }
            // Validate substring for frequency difference and continuous characters
            if (maxf - minf <= k && CheckForContinuous(tmp))
                maxi = max(maxi, (int)tmp.length());
        }
        return;
    }
    // Exclude current character
    getLongestSubSeq(alpha, tmp, start + 1, k);
    // Include current character
    tmp.push_back(alpha[start]);
    getLongestSubSeq(alpha, tmp, start + 1, k);
}
int main() {
    string alpha = "ppppqrs", tmp;
    int k = 2;
    getLongestSubSeq(alpha, tmp, 0, k);
    cout <<"The maximum length of the substring according to the given conditions is " << maxi;
    return 0;
}

输出

The maximum length of the substring according to the given conditions is 6

时间复杂度 - O(N*2N)，其中O(N)用于检查连续字符，O(2N)用于查找所有子序列。

空间复杂度 - O(N)用于存储临时子序列。

我们使用了朴素的方法来查找给定字符串的所有子序列。但是，这非常耗时。对于大型字符串，不建议使用这种方法来解决问题。