Die längste Teilsequenz, deren Zeichen mit der Teilzeichenfolge identisch sind und deren Häufigkeitsunterschied höchstens K beträgt

In diesem Problem ermitteln wir die maximale Länge der Teilsequenz so, dass sie aufeinanderfolgende Zeichen enthält und der Häufigkeitsunterschied aller Zeichen K nicht überschreitet.

Wir müssen alle möglichen Teilsequenzen einer bestimmten Zeichenfolge finden und prüfen, ob sie alle Zeichen nacheinander und mit maximalem Häufigkeitsunterschied enthält, um die Ausgabe zu erhalten.

Problemstellung- Wir erhalten eine Zeichenfolge alpha, die Kleinbuchstaben enthält. Zusätzlich wurde uns eine positive ganze Zahl K gegeben. Wir müssen die maximale Länge einer Teilsequenz einer bestimmten Zeichenfolge ermitteln, damit sie den folgenden Regeln folgt.

• Alle Vorkommen eines bestimmten Zeichens sollten aufeinanderfolgend sein.

• Der Unterschied in der Zeichenhäufigkeit darf nicht größer als K sein.

Beispiel

Eintreten

alpha = "ppppqrs", K = 2

Ausgabe

6

Erklärung – Wir können die Teilsequenz „pppqrs“ verwenden. Die maximale Zeichenhäufigkeit beträgt 3 und die minimale Zeichenhäufigkeit beträgt 1. Daher beträgt die Differenz 2. Und es enthält alle Zeichen nacheinander.

Eintreten

alpha = "abbbbc", K = 2

Ausgabe

5

Erklärung – Wir können die Teilsequenz „abbbc“ verwenden.

Eintreten

alpha = "mnnnnnnno", k = 3;

Ausgabe

7

Erklärung – Wir können die Teilsequenz „nnnnnnn“ verwenden.

Methode 1

Bei dieser Methode verwenden wir eine rekursive Funktion, um alle Teilfolgen einer bestimmten Länge zu finden. Darüber hinaus werden wir Funktionen definieren, um zu prüfen, ob eine Teilsequenz alle Zeichen nacheinander enthält. Wir werden die Kartendatenstruktur verwenden, um die maximalen und minimalen Häufigkeitsunterschiede zu berechnen.

Algorithmus

Schritt 1 – Definieren Sie die „f“-Karte, um die Häufigkeit von Zeichen zu speichern.

Schritt 2 – Wenn start gleich der Länge der temporären Zeichenfolge ist und die Zeichenfolgenlänge größer als 0 ist, befolgen Sie diese Schritte.

Schritt 3 – Initialisieren Sie die Variablen „minf“ und „maxf“, um die minimalen und maximalen Frequenzen zu speichern.

Schritt 4 – Löschen Sie die Karte und speichern Sie die Häufigkeit jedes Zeichens in der Karte.

Schritt 5 – Durchlaufen Sie die Kartenwerte und ermitteln Sie die maximalen und minimalen Häufigkeitswerte.

Schritt 6 – Wenn die maximale und minimale Frequenzdifferenz kleiner oder gleich K ist, prüfen Sie, ob die Zeichenfolge aufeinanderfolgende Zeichen enthält.

Schritt 6.1 – Definieren Sie in der Funktion checkForContinously() die Karte „pos“, um die letzte Position eines bestimmten Zeichens zu speichern.

Schritt 6.2 – Schleife durch die Schnur. Wenn das aktuelle Zeichen in der Karte vorhanden ist und der Unterschied zwischen der aktuellen Position des Zeichens und der letzten Position weniger als 1 beträgt, aktualisieren Sie die letzte Position. Andernfalls wird false zurückgegeben.

Schritt 6.3 – Fügen Sie den Charakter zur Karte hinzu, falls er nicht vorhanden ist.

Schritt 6.4 – Endlich true zurückgeben.

Schritt 7 – Wenn die Zeichenfolge aufeinanderfolgende Zeichen enthält und der Häufigkeitsunterschied weniger als K beträgt, aktualisieren Sie den Wert von „maxi“, wenn der Wert von „maxi“ kleiner als die Länge der aktuellen Teilsequenz ist.

Schritt 8 – Führen Sie einen rekursiven Aufruf durch, nachdem Sie das aktuelle Zeichen ausgeschlossen haben.

Schritt 9 – Hängen Sie das aktuelle Zeichen an das Ende der temporären Zeichenfolge an. Führen Sie außerdem einen rekursiven Aufruf mit der aktualisierten Zeichenfolge „tmp“ durch.

Beispiel

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

Ausgabe

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

Zeitkomplexität – O(N*2N), wobei O(N) zum Überprüfen aufeinanderfolgender Zeichen und O(2N) zum Finden aller Teilsequenzen dient.

Raumkomplexität – O(N) zum Speichern temporärer Teilsequenzen.

Wir verwenden eine einfache Methode, um alle Teilsequenzen einer bestimmten Zeichenfolge zu finden. Dies ist jedoch sehr zeitaufwändig. Es wird nicht empfohlen, diese Methode zur Lösung des Problems mit großen Zeichenfolgen zu verwenden.

Das obige ist der detaillierte Inhalt vonDie längste Teilsequenz, deren Zeichen mit der Teilzeichenfolge identisch sind und deren Häufigkeitsunterschied höchstens K beträgt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!