The longest subsequence whose characters are the same as the substring and whose frequency difference is at most K

In this problem, we will find the maximum length of the subsequence such that it contains consecutive characters and the frequency difference of all characters does not exceed K.

We need to find all possible subsequences of a given string and check if it contains each character consecutively and with maximum frequency difference to get the output.

Problem Statement- We are given a string alpha containing lowercase alphabetic characters. Additionally, we have been given a positive integer K. We need to find the maximum length of a subsequence of a given string such that it follows the following rules.

• All occurrences of a specific character should be consecutive.

The difference in frequency of

• characters cannot be greater than K.

Example

enter

alpha = "ppppqrs", K = 2

Output

6

Explanation - We can take the "pppqrs" subsequence. The maximum character frequency is 3 and the minimum character frequency is 1. Therefore, the difference is 2. And it contains all characters consecutively.

enter

alpha = "abbbbc", K = 2

Output

5

Explanation - We can take the "abbbc" subsequence.

enter

alpha = "mnnnnnnno", k = 3;

Output

7

Explanation - We can take the "nnnnnnn" subsequence.

method 1

In this method, we will use a recursive function to find all subsequences of a given length. Additionally, we will define functions to check if a subsequence contains all characters consecutively. We will use the map data structure to calculate the maximum and minimum frequency differences.

algorithm

Step 1 - Define the "f" mapping to store the frequency of characters.

Step 2 - If start is equal to the length of the temporary string, and the string length is greater than 0, follow these steps.

Step 3 - Initialize the "minf" and "maxf" variables to store the minimum and maximum frequencies.

Step 4 - Clear the map and store the frequency of each character in the map.

Step 5 - Loop through the map values ​​and find the maximum and minimum frequency values.

Step 6 - If the maximum and minimum frequency difference is less than or equal to K, check whether the string contains consecutive characters.

Step 6.1 - In the checkForContinously() function, define the "pos" map to store the last position of a specific character.

Step 6.2 - Traverse the string. If the current character exists in the map and the difference between the character's current position and last position is less than 1, update the last position. Otherwise, returns false.

Step 6.3 - Add the character to the map if it does not exist.

Step 6.4 - Finally return true.

Step 7 - If the string contains consecutive characters and the frequency difference is less than K, if the value of 'maxi' is less than the length of the current subsequence, update the value of 'maxi'.

Step 8 - Make a recursive call after excluding the current character.

Step 9 - Append the current characters to the end of the temporary string. Also, make a recursive call with the updated "tmp" string.

Example

#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;
}

Output

The maximum length of the substring according to the given conditions is 6

Time complexity - O(N*2N), where O(N) is used to check consecutive characters and O(2N) is used to find all subsequences.

Space complexity - O(N) to store temporary subsequences.

We use a simple method to find all subsequences of a given string. However, this is very time consuming. It is not recommended to use this method to solve the problem with large strings.

The above is the detailed content of The longest subsequence whose characters are the same as the substring and whose frequency difference is at most K. For more information, please follow other related articles on the PHP Chinese website!