子串中字元相同且頻率差最多為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)用於儲存臨時子序列。

我們使用了樸素的方法來查詢給定字串的所有子序列。但是，這非常耗時。對於大型字串，不建議使用這種方法來解決問題。