4. Týrajú ma hladom vzorové riešenie

10 2
abbcbadabc

6

20 5
9z2bX3dQquQevLFRmhYH

7

Úlohu zo zadania môžeme preformulovať tak, že chceme nájsť najdlhšiu súvislú podpostupnosť vstupného slova skladajúcu sa najviac z \(k+1\) rôznych písmen.

Totiž ak \(k\) písmen prepíšeme na to \(k+1\)vé, budeme mať úsek písmen, ktoré vyzerajú rovnako.

Priamočiare riešenie

Ak by sme vedeli kde hladaný interval začína, vieme pomerne jednoducho zistiť aký je dlhý. Skúsime preto od každého písmena na vstupe spočítať aký dlhý interval by na ňom mohol začínať a riešením bude ich maximum.

Skúsime to teda naprogramovať.

Na pamätanie si, či sme dané písmenko už zarátali nám pomôže set, do ktorého budeme pridávať každé písmenko. Set je štruktúra ktorá ukladá iba rôzne prvky, preto sa stačí po každom vložení písmena pozrieť na veľkosť setu. Ak veľkosť setu presiahne \(k+1\), vieme, že už v ňom máme viac ako \(k+1\) písmeniek, teda posledné písmenko už do aktuálnej postupnosti patriť nemôže.

Toto riešenie má časovú zložitosť \(O(n^2)\)¹ a pamäťovu \(O(n)\). Mohli ste zaň získať \(4\) body.

Ide to ale aj lepšie

Keď sme narazili na \(k+2\) písmeno v predošlom riešení, museli sme celý interval zahodiť a začať od začiatku. Po krátkom zamyslení však zistíme, že ten nasledujúci interval sa nebude veľmi líšiť. Môžu nastať dve situácie. Buď sa prvé písmenko v intervale ešte niekde nachádza a teda nasledujúci interval bude rovnaký, alebo odstránením prvého písmena nám klesne aj počet rôznych písmen v sete a môžeme interval predĺžiť.

Aby sme mohli takto postupovať, musíme si namiesto setu ale pamätať aj počet výskytov v intervale pre každé písmeno. Rôznych znakov môže byť najviac \(62\) (čísla, veľká a malá anglická abeceda), takže najlepšie bude použiť statické pole. Ak ho spravíme o niečo dlhšie, môžeme do neho indexovať priamo ASCII hodnotou znaku. Namiesto veľkosti setu si potom potrebujeme v nejakej premennej pamätať počet rôznych písmen v intervale.

Vstupné slovo budeme teda pechádzať z ľava do prava a to nasledovne:

Kým je počet menší ako \(k+2\), budeme sa koncom hýbať doprava. Keď sa pohneme, prečítame písmenko a započítame jeho výskyt. Ak je prvý, počet rôznych písmen zväčšíme o jeden.

Ak sa nám ale stalo, že počet je väčší ako \(k+1\), máme maximálny interval a môžeme posunúť začiatok. Písmeno ktoré na začiatku intervalu strácame odrátame z výskytov a skontrolujeme či bolo posledné. Ak sme zistili, že to bolo posledné písmeno toho druhu v intervale, znížime počet rôznych písmen o jeden môžeme zase posunúť koniec. Inak sa počet rôznych písmen nezmenil a koniec nevieme posunúť, takže pokračueme v posúvaní začiatku. Medzičasom si budeme pamätať maximálnu dĺžku intervalu. Takémuto postupu sa niekedy hovorí aj dvaja bežci.

Časová a pamäťová zložitosť

V tomto riešení máme dva indexy do pola ktoré postupne posúvame od začiatku po koniec. Každý teda nezávysle na druhom spraví \(O(n)\) krokov. Okrem toho používame statické pole na počet výskytov písmen, do ktorého však indexujeme iba keď posúvame jeden z indexov, teda časovú zložitosť to nemení a ostáva \(O(n)\).

Skúseného riešiteľa neprekvapí, že pamäťová zložitosť je tiež \(O(n)\)² nakoľko viac pamäte v čase \(O(n)\) nestihneme ani naplniť.

n, k = map(int, input().split())
w = input()
u = 0
s = 0
e = 0
ans = 1
ans_start = 0
new_ans = 0
c = [0]*255
k+=1

for e in range(len(w)):
	if c[ord(w[e])] == 0:
		u+=1
	c[ord(w[e])]+=1

	while u > k:
		c[ord(w[s])]-=1
		if c[ord(w[s])] == 0:
			u-=1
		s+=1

	new_ans = e-s+1;
	
	if new_ans > ans:
		ans = new_ans;

print(ans)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string w;
int k, n, u = 0, s = 0, e = 0, ans = 1, ans_start = 0, new_ans = 0;
vector<int> c(255);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k >> w;
	k++;

	for (unsigned int e = 0; e < n; e++) {
		if (!c[w[e]]) u++;
		c[w[e]]++;

		while (u > k) {
			c[w[s]]--;
			if (!c[w[s]]) u--;
			s++;
		}
		
		new_ans = e-s+1;
		
		if (new_ans > ans) {
			ans = new_ans;
			//ans_start = s;
		}
	}

	cout << ans << '\n';
}