# PBinfo #3800 – DistinctLetters – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Scrieți funcția care are antetul:

int DistinctLetters(string s, int L, int U)
Funcția va returna numărul de secvențe care au între L și U litere distincte. Într-o secvență fiecare literă se va număra o singură dată. De exemplu, s="capac" are 3 litere distincte.

Restricții și precizări

s va conține numai litere mici
s conține cel puțin o literă și cel mult 30.000 de litere
1 ≤ L < U ≤ 26
Puteți utiliza în rezolvare orice structură de date

Exemplu:
Dacă s="aabbc", L=1 și U=2, atunci funcția va returna 13, secvențele care au între 1 și 2 litere distincte fiind: a, aa, aab, aabb, a, ab, abb, b, bb, bbc, b, bc, c.

Important
Soluţia propusă va conţine doar funcţia cerută. Prezenţa în soluţie a altor instrucţiuni poate duce la erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

## Cod sursă C++

```cpp
int DistinctLetters(string s, int L, int U)
{
    int answer = 0;
    int cnt, j, i, n;
    int fr[26] = {0};
    n = s.length();
    // numaram cate secvente au cel mult U litere distincte
    cnt = j = 0;
    for (i = 0; i < n; i++)
    {
        fr[s[i] - 'a']++;
        if (fr[s[i] - 'a'] == 1) cnt++;
        while (cnt > U)
        {
            fr[s[j] - 'a']--;
            if (fr[s[j] - 'a'] == 0) cnt--;
            j++;
        }
        answer += (i - j + 1);
    }
    // scadem secventele care au cel mult L - 1 litere distincte
    for (i = 0; i < 26; i++)
        fr[i] = 0;
    cnt = j = 0;
    for (i = 0; i < n; i++)
    {
        fr[s[i] - 'a']++;
        if (fr[s[i] - 'a'] == 1) cnt++;
        while (cnt > L - 1)
        {
            fr[s[j] - 'a']--;
            if (fr[s[j] - 'a'] == 0) cnt--;
            j++;
        }
        answer -= (i - j + 1);
    }
    return answer;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3800)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3800/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3800/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)