virus

Intuiție: ce înseamnă, de fapt, o „mutație”

Hai să traducem enunțul în limbaj simplu. Avem un cod de referință — virusul pandemic, să-i spunem $p$. Primim o listă de coduri și, pentru fiecare, ne punem o singură întrebare: seamănă „aproape perfect” cu $p$?

„Aproape perfect” are aici o definiție foarte precisă, formată din două condiții care trebuie îndeplinite în același timp:

1. Aceeași lungime — codul are exact câte litere are $p$. Dacă e mai scurt sau mai lung, nici nu mai discutăm.
2. Exact o singură literă diferită — pe toate pozițiile coincide cu $p$, mai puțin una.

Imaginează-ți că suprapui cele două șiruri, literă peste literă, ca pe două rânduri într-un tabel. O mutație este un cod care, suprapus peste $p$, are fix o coloană unde literele nu se potrivesc. Nici zero (atunci ar fi identic, nu mutație), nici două sau mai multe.

Pentru abac, șirul Bbac este mutație: prima literă diferă ($a$ devine $B$), restul coincide. În schimb abac (identic) nu e mutație, iar BBac (două diferențe) nu e mutație.

Ideea cheie

Toată problema se reduce la o funcție mică, pe care o aplicăm pe fiecare cod din listă:

Numără pozițiile pe care codul diferă de $p$. Este mutație dacă și numai dacă lungimile sunt egale și numărul de diferențe este exact $1$.

Odată ce avem această funcție, cele două cerințe devin simple:

• C=1 — câte mutații sunt în listă? Trecem o dată prin listă și numărăm câte coduri trec testul. Atenție: numărăm aparițiile, nu mutațiile distincte — dacă același cod-mutație apare de trei ori, contează de trei ori.
• C=2 — care mutație apare de cele mai multe ori? Ținem un contor de frecvențe (un map cu cheie șirul și valoare numărul de apariții). La final alegem mutația cu frecvența maximă; la egalitate, pe cea mai mică lexicografic.

Algoritmul pas cu pas (pe Exemplul 2)

Să urmărim concret cerința $C=2$ cu pandemicul abcD și lista abcdD, XbcD, Xc, XbcD, aXcD, aXcD, aXc, ab. Pandemicul are lungimea $4$.

1. abcdD — lungime $5 \neq 4$. Eliminat din start, fără să comparăm litere.
2. XbcD — lungime $4$. Comparăm: poziția 1 are X în loc de a (diferență), pozițiile 2, 3, 4 coincid. O singură diferență → mutație. În map: XbcD ajunge la $1$.
3. Xc — lungime $2 \neq 4$. Eliminat.
4. XbcD — din nou mutație. În map: XbcD ajunge la $2$.
5. aXcD — lungime $4$, diferă doar pe poziția 2 (X față de b). Mutație. În map: aXcD ajunge la $1$.
6. aXcD — mutație. În map: aXcD ajunge la $2$.
7. aXc — lungime $3 \neq 4$. Eliminat.
8. ab — lungime $2 \neq 4$. Eliminat.

La final avem două mutații cu frecvență maximă $2$: XbcD și aXcD. Departajăm lexicografic: comparăm prima literă, X (cod ASCII $88$) față de a (cod ASCII $97$). Cum $88 < 97$, șirul XbcD este mai mic, deci el este răspunsul.

Acesta este și momentul cel mai înșelător din problemă: intuiția „de zi cu zi” spune că a vine înaintea lui X (alfabetul mic pare „mai la început”), dar codul ASCII pune toate majusculele ($65$–$90$) înaintea tuturor minusculelor ($97$–$122$). Ordinea reală este deci $A < B < \dots < Z < a < b < \dots < z$.

De ce e corect

Corectitudinea funcției de verificare vine direct din definiție: o mutație are, prin enunț, exact o poziție diferită la lungimi egale — iar noi exact asta numărăm. Verificarea lungimii înainte de a compara caractere nu e doar o optimizare, ci o condiție necesară: șiruri de lungimi diferite nu pot fi „suprapuse” și nu pot fi mutații, indiferent câte litere ar avea în comun.

Pentru $C=2$, un map<string,int> reține fidel câte ori a apărut fiecare mutație, deoarece incrementăm contorul la fiecare apariție validă. Alegerea răspunsului parcurge toate cheile și păstrează perechea cu frecvența maximă; la frecvențe egale reține cheia mai mică. Aici intervine un detaliu elegant: în C++ std::string se compară chiar după codul ASCII, iar std::map<string,int> ține cheile deja sortate crescător. Astfel, comparația standard < este exact ordinea cerută de problemă, fără să scriem nimic special.

Complexitate

Notăm cu $N$ numărul de coduri și cu $L$ lungimea maximă a unui cod ($L \leq 200$).

• Verificarea unui cod costă $O(L)$ — o singură trecere prin caractere (cu ieșire devreme când diferențele depășesc $1$).
• C=1 costă $O(N \cdot L)$: aplicăm verificarea pe fiecare cod.
• C=2 adaugă operațiile pe map. Fiecare inserare/căutare compară chei de lungime $L$ și face $O(\log N)$ pași, deci $O(N \cdot L \log N)$ în total.

Cu $N \leq 50\,000$ și $L \leq 200$, chiar și cazul $C=2$ rămâne în jur de câteva milioane de operații — mult sub limita de timp.