De ce contează?
Ai un coș cu bile colorate și vrei să știi câte sunt din fiecare culoare. Nu numeri de fiecare dată tot coșul pentru o singură culoare — ar fi muncă pe degeaba. Pui în față 26 de cutiuțe, câte una pentru fiecare culoare, treci o singură dată prin coș și, la fiecare bilă, adaugi un punct în cutiuța potrivită. La final, fiecare cutiuță îți spune direct câte bile de culoarea ei există.
Intuiția
Numărarea aparițiilor fiecărei litere dintr-un șir este exact problema bilelor: cele 26 de cutiuțe sunt un tablou fr[26], iar fiecare literă din șir adaugă un punct în cutiuța ei. În loc să cauți de fiecare dată prin tot șirul „de câte ori apare litera asta?”, ții un contor per literă și îl crești pe măsură ce înaintezi. O singură trecere prin șir umple toate contoarele deodată.
Vezi cum funcționează
Folosește ← și → ca să pășești prin algoritm, sau Redă pentru animație. Urmărește cum, la fiecare caracter citit, crește exact bara contorului din dreptul literei lui.
Prima idee: pentru fiecare literă din alfabet, parcurgi tot șirul și numeri câte apariții are. Întâi numeri toți de „a”, apoi reiei șirul de la capăt și numeri toți de „b”, și tot așa până la „z”.
Faci aceeași muncă de 26 de ori: parcurgi șirul o dată pentru fiecare literă, deci O(26·n) operații. Mai rău, repeți treceri inutile chiar și pentru litere care nu apar deloc — câtă vreme exiști un singur contor pe care îl reaprinzi mereu de la zero, irosești efort.
N-ai nevoie de 26 de treceri. La un singur pas peste șir, fiecare caracter „știe” singur în ce contor trebuie să se adauge: litera ne dă direct poziția. Folosind c - 'a' ca index, transformi litera într-un număr între 0 și 25 și nimerești cutiuța potrivită instant.
Ții un tablou fr[26] pornit de la zero și parcurgi șirul o singură dată. La fiecare literă faci fr[s[i] - 'a']++. Asta umple toate cele 26 de contoare deodată, în O(n).
Algoritmul pas cu pas
Fie șirul abracadabra. Pornim cu tabloul fr plin de zerouri și citim caracter cu caracter; fiecare literă crește contorul ei:
a→fr[0]++(a devine 1)b→fr[1]++(b devine 1)r→fr[17]++(r devine 1)a→fr[0]++(a devine 2)c→fr[2]++(c devine 1)a→fr[0]++(a devine 3)d→fr[3]++(d devine 1)a→fr[0]++(a devine 4)b→fr[1]++(b devine 2)r→fr[17]++(r devine 2)a→fr[0]++(a devine 5)
După ce am terminat de parcurs tot șirul, primele poziții din tabloul de frecvențe arată așa (afișez doar literele care apar — a, b, c, d, r):
| fr | 5 | 2 | 1 | 1 | 2 |
| litera | a | b | c | d | r |
a | r |
Un test rapid de corectitudine: suma tuturor contoarelor trebuie să fie egală cu lungimea șirului. Aici 5 + 2 + 2 + 1 + 1 = 11, exact câte litere are abracadabra. Dacă suma nu se potrivește, ai pierdut sau ai numărat de două ori undeva.
Implementare C++
#include <iostream>
#include <string>
using namespace std;
int main() {
string s = "abracadabra"; // exemplu concret
int fr[26] = {0}; // 26 contoare, toate pornite de la 0
// o singura parcurgere: fiecare litera isi creste contorul
for (int i = 0; i < (int)s.size(); i++) {
fr[s[i] - 'a']++; // 'a'->0, 'b'->1, ..., 'z'->25
}
// afisam doar literele care apar cel putin o data
for (int c = 0; c < 26; c++) {
if (fr[c] > 0) {
cout << char('a' + c) << ": " << fr[c] << "\n";
}
}
// a: 5 b: 2 c: 1 d: 1 r: 2
return 0;
}Cheia este fr[s[i] - 'a']: litera s[i] se scade din 'a', deci 'a' devine indexul 0, 'b' indexul 1 și așa mai departe. O singură instrucțiune, fr[s[i] - 'a']++, face toată numărarea.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Orice caz | O(n) | O(26) |
Parcurgem șirul o singură dată (n este lungimea lui), iar tabloul de frecvențe are mereu 26 de poziții, indiferent cât de lung e șirul — spațiu constant. Asta bate clar abordarea naivă O(26·n), care reparcurge șirul pentru fiecare literă.
Trei capcane clasice la tabloul de frecvențe:
- Uiți să inițializezi
frcu 0. Un tablou local neinițializat conține valori-gunoi; fărăint fr[26] = {0};, fiecarefr[k]++adună peste un număr aleatoriu. Pornește mereu de la zero. - Indexezi fără
- 'a'. Dacă scriifr[s[i]]++, indexul devine codul ASCII al literei (97 pentrua), care iese din tabloul de 26 de poziții — acces în afara vectorului, comportament nedefinit. Foloseștefr[s[i] - 'a']. - Amesteci majuscule cu minuscule.
'A'și'a'au coduri diferite, deci ajung în cutiuțe diferite (sau în afara tabloului). Dacă vrei să le tratezi la fel, transformă întâi totul în minuscule; dacă ai și majuscule de numărat separat, folosește un tabloufr[256]indexat direct după codul caracterului.