在这个问题中,我们会找到子序列的最大长度,使其包含连续的字符,并且所有字符的频率差不会超过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 <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) 来存储临时子序列。
我们使用简单的方法来查找给定字符串的所有子序列。然而,这是非常耗时的。不建议对大字符串使用此方法来解决问题。