最长的子序列，其字符与子串相同，并且频率差最多为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

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

ToonMe

一款风靡Instagram的软件，一键生成卡通头像

下载

算法

第 1 步 - 定义“f”映射来存储字符的频率。

步骤 2 - 如果开始等于临时字符串的长度，并且字符串长度大于 0，请按照以下步骤操作。

第 3 步 - 初始化“minf”和“maxf”变量来存储最小和最大频率。

第 4 步- 清除地图，并将每个字符的出现频率存储在地图中。

第 5 步 - 遍历地图值并找到最大和最小频率值。

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

步骤 6.1 - 在 checkForContinously() 函数中，定义“pos”映射来存储特定字符的最后位置。

步骤 6.2 - 遍历字符串。如果地图中存在当前字符，并且该字符的当前位置与最后位置之间的差值小于1，则更新最后位置。否则，返回 false。

步骤 6.3 - 如果角色不存在，则将角色添加到地图。

步骤 6.4 - 最后返回 true。

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

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

步骤 9 - 将当前字符附加到临时字符串的末尾。另外，使用更新后的“tmp”字符串进行递归调用。

示例

#include 
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 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 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) 来存储临时子序列。

我们使用简单的方法来查找给定字符串的所有子序列。然而，这是非常耗时的。不建议对大字符串使用此方法来解决问题。