最長的子序列，其字元與子字串相同，且頻率差最多為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

在這種方法中，我們將使用遞歸函數來尋找給定長度的所有子序列。此外，我們將定義函數來檢查子序列是否連續包含所有字元。我們將使用地圖資料結構來計算最大和最小頻率差異。

演算法

第 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) 來儲存暫存子序列。

我們使用簡單的方法來尋找給定字串的所有子序列。然而，這是非常耗時的。不建議對大字串使用此方法來解決問題。

以上是最長的子序列，其字元與子字串相同，且頻率差最多為K的詳細內容。更多資訊請關注PHP中文網其他相關文章！