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