在这个问题中，我们会找到子序列的最大长度，使其包含连续的字符，并且所有字符的频率差不会超过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
在这种方法中，我们将使用递归函数来查找给定长度的所有子序列。此外，我们将定义函数来检查子序列是否连续包含所有字符。我们将使用地图数据结构来计算最大和最小频率差异。
算法
第 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 substringbool 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) 来存储临时子序列。
我们使用简单的方法来查找给定字符串的所有子序列。然而，这是非常耗时的。不建议对大字符串使用此方法来解决问题。
以上就是最长的子序列，其字符与子串相同，并且频率差最多为K的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444716.html
微信扫一扫 
支付宝扫一扫 
