Frecvențe

Intuiția

Un șir de caractere e o înșiruire de litere, dar de multe ori nu te interesează ordinea lor, ci de câte ori apare fiecare. Ții un singur tablou mic, cu o căsuță pentru fiecare literă posibilă, și parcurgi șirul o dată: pentru fiecare literă, mai pui un băț în căsuța ei. La final, tabloul îți spune totul despre compoziția șirului — fără să-l mai atingi. Acest tablou se numește vector de frecvențe.

Vezi cum funcționează

Urmărește cum o singură trecere prin șir umple căsuțele tabloului de frecvențe: fiecare literă citită incrementează exact o căsuță, cea care îi corespunde.

Algoritmul pas cu pas

Fie șirul abracadabra (11 litere). Pornim cu tabloul freq plin de zerouri și parcurgem litera cu literă, incrementând de fiecare dată căsuța s[i] - 'a'.

Prima literă e a, deci a - 'a' = 0. Incrementăm căsuța 0:

Citim b (b - 'a' = 1), apoi r (r - 'a' = 17), apoi din nou a. După patru litere citite (a b r a) avem doi de a, un b, un r:

Continuăm cu c a d a b r a. La final, fiecare literă din abracadabra și-a pus toate bețele:

Implementare C++

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

int main() {
    char s[] = "abracadabra";
    int n = strlen(s);

    // o casuta pentru fiecare litera mica: a->0, b->1, ..., z->25
    int freq[26] = {0};   // initializare cu 0, esential

    // o singura trecere: fiecare litera incrementeaza casuta ei
    for (int i = 0; i < n; i++) {
        freq[s[i] - 'a']++;
    }

    // afisam doar literele care chiar apar
    for (int c = 0; c < 26; c++) {
        if (freq[c] > 0) {
            cout << (char)('a' + c) << ": " << freq[c] << "\n";
        }
    }
    // a: 5  b: 2  c: 1  d: 1  r: 2

    // litera cea mai frecventa
    int maxim = 0;
    for (int c = 1; c < 26; c++) {
        if (freq[c] > freq[maxim]) {
            maxim = c;
        }
    }
    cout << "Cea mai frecventa: " << (char)('a' + maxim) << "\n";
    // Cea mai frecventa: a

    return 0;
}

Pentru a verifica dacă două șiruri sunt anagrame, construiești câte un tablou de frecvențe pentru fiecare și compari cele 26 de poziții:

bool suntAnagrame(const char a[], const char b[]) {
    int fa[26] = {0}, fb[26] = {0};
    for (int i = 0; a[i]; i++) fa[a[i] - 'a']++;
    for (int i = 0; b[i]; i++) fb[b[i] - 'a']++;
    for (int c = 0; c < 26; c++) {
        if (fa[c] != fb[c]) return false;   // o diferenta -> nu sunt anagrame
    }
    return true;
}
// suntAnagrame("listen", "silent") -> true

Complexitate

Notăm n lungimea șirului și A mărimea alfabetului (26 pentru litere mici, 256 pentru toate caracterele ASCII).

Tabloul are mărime fixă (26 sau 256), independentă de n, deci spațiul e practic constant. Abordarea naivă, cu reparcurgere pentru fiecare literă, ar fi fost O(n × A) — același rezultat, mult mai lent.