La sous-séquence la plus longue dont les caractères sont les mêmes que la sous-chaîne et dont la différence de fréquence est d'au plus K

Dans ce problème, nous trouverons la longueur maximale de la sous-séquence telle qu'elle contienne des caractères consécutifs et que la différence de fréquence de tous les caractères ne dépasse pas K.

Nous devons trouver toutes les sous-séquences possibles d'une chaîne donnée et vérifier si elle contient chaque caractère consécutivement et avec une différence de fréquence maximale pour obtenir le résultat.

Énoncé du problème- Nous recevons une chaîne alpha contenant des caractères alphabétiques minuscules. De plus, on nous a donné un entier positif K. Nous devons trouver la longueur maximale d’une sous-séquence d’une chaîne donnée telle qu’elle suive les règles suivantes.

• Toutes les occurrences d'un caractère spécifique doivent être consécutives.

• La différence de fréquence des caractères ne peut pas être supérieure à K.

Exemple

Entrez

alpha = "ppppqrs", K = 2

Sortie

6

Explication - On peut prendre la sous-séquence "pppqrs". La fréquence maximale des caractères est de 3 et la fréquence minimale des caractères est de 1. La différence est donc de 2. Et il contient tous les caractères consécutivement.

Entrez

alpha = "abbbbc", K = 2

Sortie

5

Explication - On peut prendre la sous-séquence "abbbc".

Entrez

alpha = "mnnnnnnno", k = 3;

Sortie

7

Explication - On peut prendre la sous-séquence "nnnnnnn".

Méthode 1

Dans cette méthode, nous utiliserons une fonction récursive pour trouver toutes les sous-séquences d'une longueur donnée. De plus, nous définirons des fonctions pour vérifier si une sous-séquence contient tous les caractères consécutivement. Nous utiliserons la structure des données cartographiques pour calculer les différences de fréquence maximales et minimales.

Algorithme

Étape 1 - Définissez la carte "f" pour stocker la fréquence des caractères.

Étape 2 - Si start est égal à la longueur de la chaîne temporaire et que la longueur de la chaîne est supérieure à 0, suivez ces étapes.

Étape 3 - Initialisez les variables "minf" et "maxf" pour stocker les fréquences minimales et maximales.

Étape 4- Effacez la carte et stockez la fréquence de chaque personnage dans la carte.

Étape 5 - Parcourez les valeurs de la carte et recherchez les valeurs de fréquence maximale et minimale.

Étape 6 - Si la différence de fréquence maximale et minimale est inférieure ou égale à K, vérifiez si la chaîne contient des caractères consécutifs.

Étape 6.1 - Dans la fonction checkForContinously(), définissez la carte "pos" pour stocker la dernière position d'un caractère spécifique.

Étape 6.2 - Faites une boucle sur la ficelle. Si le caractère actuel existe dans la carte et que la différence entre la position actuelle du personnage et sa dernière position est inférieure à 1, mettez à jour la dernière position. Sinon, renvoie faux.

Étape 6.3 - Ajoutez le personnage à la carte s'il n'existe pas.

Étape 6.4 - Enfin, retournez vrai.

Étape 7 - Si la chaîne contient des caractères consécutifs et que la différence de fréquence est inférieure à K, mettez à jour la valeur de 'maxi' si la valeur de 'maxi' est inférieure à la longueur de la sous-séquence actuelle.

Étape 8 - Effectuez un appel récursif après avoir exclu le personnage actuel.

Étape 9 - Ajoutez le caractère actuel à la fin de la chaîne temporaire. Effectuez également un appel récursif avec la chaîne "tmp" mise à jour.

Exemple

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

Sortie

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

Complexité temporelle - O(N*2N), où O(N) pour vérifier les caractères consécutifs et O(2N) pour trouver toutes les sous-séquences.

Complexité spatiale - O(N) pour stocker la sous-séquence temporaire.

Nous utilisons une méthode simple pour trouver toutes les sous-séquences d'une chaîne donnée. Cependant, cela prend beaucoup de temps. Il n'est pas recommandé d'utiliser cette méthode pour résoudre le problème des grandes chaînes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!