Frecvențe — câte de fiecare caracter

De ce contează?

Imaginează-ți că golești o pungă de bile colorate pe masă și vrei să știi câte ai din fiecare culoare. Nu le ții minte una câte una — pui câte o liniuță în dreptul fiecărei culori de fiecare dată când vezi o bilă. Asta este un vector de frecvență.

Ce este un vector de frecvență?

Un vector de frecvență este un tablou în care poziția i ține de câte ori apare caracterul i. Pentru litere mici, poziția c - 'a' corespunde literei c: frec[0] numără pe 'a', frec[1] pe 'b', și așa mai departe.

Observația-cheie

Ideea-cheie: în loc să cauți de fiecare dată „de câte ori apare litera X” (parcurgând tot șirul mereu), parcurgi o singură dată și incrementezi o celulă. Numărarea devine O(n) în loc de O(26n).

Algoritmul pas cu pas

Fie cuvântul "banana". Pornim cu toate frecvențele 0 și parcurgem:

b → frec['b'-'a'] = frec[1]++ → b:1
a → frec[0]++ → a:1
n → frec[13]++ → n:1
a → a:2
n → n:2
a → a:3

La final: a apare de 3 ori, n de 2 ori, b o dată.

3	1	0	0	...	2	...
a	b	c	d	...	n	...

Vectorul de frecvență pentru „banana”: frec[a]=3, frec[b]=1, frec[n]=2.

Implementare C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s = "banana";
    int frec[26] = {0};            // initializare cu 0, important!

    for (char c : s) {
        frec[c - 'a']++;           // c-'a' = pozitia literei (0..25)
    }

    for (int i = 0; i < 26; i++) {
        if (frec[i] > 0) {
            cout << (char)('a' + i) << ": " << frec[i] << "\n";
        }
    }
    // a: 3
    // b: 1
    // n: 2
    return 0;
}

De ce frec[26] = {0}? Dacă uiți inițializarea, vectorul local conține gunoi din memorie, iar numărătoarea pornește de la valori aleatorii.

Aplicație: sunt anagrame?

Două cuvinte sunt anagrame dacă au aceleași litere cu aceleași frecvențe ("listen" și "silent"). Compari pur și simplu vectorii de frecvență:

#include <iostream>
#include <string>
using namespace std;

bool anagrame(string a, string b) {
    if (a.size() != b.size()) return false;   // lungimi diferite -> nu
    int frec[26] = {0};
    for (char c : a) frec[c - 'a']++;          // adauga din a
    for (char c : b) frec[c - 'a']--;          // scade din b
    for (int i = 0; i < 26; i++)
        if (frec[i] != 0) return false;        // ramas dezechilibru
    return true;
}

int main() {
    cout << anagrame("listen", "silent") << "\n";  // 1
    cout << anagrame("info",   "ifno")   << "\n";  // 1
    return 0;
}

Complexitate

Operație	Timp	Spațiu
Construirea frecvențelor	O(n)	O(alfabet)
Verificare anagramă	O(n)	O(26)

Greșeli frecvente

Greșeli frecvente de concurs:

Vector neinițializat: int frec[26]; fără = {0} numără peste gunoi.
Dimensiune greșită: pentru litere mari ȘI mici sau caractere oarecare ai nevoie de frec[256], indexat cu (unsigned char)c, nu cu c - 'a'.
Index negativ: dacă în șir apar și spații sau cifre, c - 'a' devine negativ → acces în afara vectorului. Filtrează cu isalpha sau folosește 256.
Overflow la șiruri uriașe: pentru n peste ~2·10⁹ apariții folosește long long.

Vizualizare

Urmărește cum se completează vectorul de frecvență, caracter cu caracter:

Indiciu

Folosește ← și → pentru a avansa pas cu pas. Observă cum o singură celulă crește la fiecare caracter citit — o singură trecere prin șir.

Recapitulare

Un vector de frecvență numără aparițiile fiecărui caracter într-o singură parcurgere O(n), indexând cu c - 'a'.
Inițializează mereu cu {0} și alege dimensiunea după alfabetul real (26 sau 256).
Egalitatea vectorilor de frecvență = test rapid de anagramă.