Najkraća podniska koja sadrži sve date karaktere

Pitanje ili opis problema

[koristite ovaj template za postavljanje tema u kategoriji Pitanja i problemi]
Pitanje je u vezi sa zadatkom “Najkraća podniska koja sadrži sve date karaktere”. Ideja mi je bila da prvo prodjem kroz drugi string, izbrojim koliko odredjenih karaktera ima string i sacuvan taj broj u niz u kojoj svaki ASCII kod pokazuje koliko puta se taj karakter pojavljuje u stringu. Isto tako sam uradio i sa drugim stringom. Potom bih prosao toj prvi string, stavio dva pokazivaca na krajeve i zatim ih povecavao/smanjivao ako pokazan karakter uopste ne pripada drugom stringu ili ako je u ostatku prvog stringa jos uvek ostalo dovoljno karaktera istog tipa da se pokazivac moze povecati/smanjiti i time smanjiti najmanja moguca podniska. Medjutim, u pola slucajeva dobijam WA, pri cemu ne razumem zasto sam to dobio.

Kod:

string s, k;
bool check1, check2, flag = false;
cin >> s >> k;

int res = s.length();

int arr1[256] = {0};
int arr2[256] = {0};

for (int i = 0; i < k.length(); ++i) {
    ++arr1[k[i]];
}

for (int i = 0; i < s.length(); ++i) {
    ++arr2[s[i]];
}

for (int i = 0; i < k.length(); ++i) {
    if (arr2[k[i]] < arr1[k[i]]) {
        flag = true;
        break;
    }
}

int l = 0, r = s.length() - 1;

if (!flag) {
while (l < r) {
    check1 = false, check2 = false;
    if (!arr1[s[l]] || arr2[s[l]] > arr1[s[l]]) {
        if (arr1[s[l]]) {
            --arr2[s[l]];
        }
        ++l;
        --res;
        check1 = true;
    }

    if (!arr1[s[r]] || arr2[s[r]] > arr1[s[r]]) {
        if (arr1[s[r]]) {
            --arr2[s[r]];
        }
        --r;
        --res;
        check2 = true;
    }

    if (!check1 && !check2) {
        break;
    }
}
}

if (flag) {
    cout << "nema";
} else {
    cout << res;
}

}

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/biblioteka/r/problemi/zbirka-napredni-nivo/najkraca_podniska_koji_sadrzi_date_karaktere

nije ok algoritam:
npr za
abcccaacccab
ab
vraća 5

ovde ti je objašnjen jedan od načina https://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/

1 Like