Susunan terpanjang yang aksaranya sama dengan subrentetan dan perbezaan frekuensinya paling banyak K

Dalam masalah ini, kita akan mendapati panjang maksimum bagi urutan yang mengandungi aksara berturut-turut dan perbezaan kekerapan semua aksara tidak melebihi K.

Kita perlu mencari semua kemungkinan urutan rentetan yang diberikan dan menyemak sama ada ia mengandungi setiap aksara secara berturutan dan dengan perbezaan frekuensi maksimum untuk mendapatkan output.

Pernyataan Masalah- Kami diberi rentetan alfa yang mengandungi aksara abjad huruf kecil. Selain itu, kami telah diberi integer positif K. Kita perlu mencari panjang maksimum bagi urutan rentetan tertentu supaya ia mengikut peraturan berikut.

• Semua kejadian watak tertentu hendaklah berturut-turut.

• Perbezaan kekerapan aksara tidak boleh lebih besar daripada K.

Contoh

Masuk

alpha = "ppppqrs", K = 2

Output

6

Penjelasan - Kita boleh ambil "pppqrs" seterusnya. Kekerapan aksara maksimum ialah 3 dan kekerapan aksara minimum ialah 1. Oleh itu, perbezaannya ialah 2. Dan ia mengandungi semua aksara berturut-turut.

Masuk

alpha = "abbbbc", K = 2

Output

5

Penjelasan - Kita boleh ambil urutan "abbbc".

Masuk

alpha = "mnnnnnnno", k = 3;

Output

7

Penjelasan - Kita boleh ambil "nnnnnnn" seterusnya.

Kaedah 1

Dalam kaedah ini, kita akan menggunakan fungsi rekursif untuk mencari semua urutan panjang tertentu. Selain itu, kami akan mentakrifkan fungsi untuk menyemak sama ada urutan mengandungi semua aksara secara berturut-turut. Kami akan menggunakan struktur data peta untuk mengira perbezaan frekuensi maksimum dan minimum.

Algoritma

Langkah 1 - Tentukan peta "f" untuk menyimpan kekerapan aksara.

Langkah 2 - Jika permulaan adalah sama dengan panjang rentetan sementara, dan panjang rentetan lebih besar daripada 0, ikut langkah ini.

Langkah 3 - Mulakan pembolehubah "minf" dan "maxf" untuk menyimpan frekuensi minimum dan maksimum.

Langkah 4- Kosongkan peta dan simpan kekerapan setiap aksara dalam peta.

Langkah 5 - Gelung nilai peta dan cari nilai kekerapan maksimum dan minimum.

Langkah 6 - Jika perbezaan frekuensi maksimum dan minimum adalah kurang daripada atau sama dengan K, semak sama ada rentetan mengandungi aksara berturut-turut.

Langkah 6.1 - Dalam fungsi checkForContinously(), tentukan peta "pos" untuk menyimpan kedudukan terakhir aksara tertentu.

Langkah 6.2 - Gelung melalui rentetan. Jika aksara semasa wujud dalam peta dan perbezaan antara kedudukan semasa watak dan kedudukan terakhir adalah kurang daripada 1, kemas kini kedudukan terakhir. Jika tidak, pulangan palsu.

Langkah 6.3 - Tambahkan aksara pada peta jika ia tidak wujud.

Langkah 6.4 - Akhirnya kembali benar.

Langkah 7 - Jika rentetan mengandungi aksara berturutan dan perbezaan frekuensi kurang daripada K, kemas kini nilai 'maxi' jika nilai 'maxi' kurang daripada panjang jujukan semasa.

Langkah 8 - Buat panggilan rekursif selepas mengecualikan aksara semasa.

Langkah 9 - Tambahkan aksara semasa pada penghujung rentetan sementara. Juga, buat panggilan rekursif dengan rentetan "tmp" yang dikemas kini.

Contoh

#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

Kerumitan masa - O(N*2N), di mana O(N) untuk menyemak aksara berturut-turut dan O(2N) untuk mencari semua urutan.

Kerumitan ruang - O(N) untuk menyimpan urutan sementara.

Kami menggunakan kaedah mudah untuk mencari semua urutan rentetan yang diberikan. Walau bagaimanapun, ini sangat memakan masa. Ia tidak disyorkan untuk menggunakan kaedah ini untuk menyelesaikan masalah dengan rentetan besar.

Atas ialah kandungan terperinci Susunan terpanjang yang aksaranya sama dengan subrentetan dan perbezaan frekuensinya paling banyak K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!