3033 - criptografie

Zedd a descoperit frumusețea aplicațiilor din domeniul criptografiei. Astfel, el și-a activat abilitățile de hacker și s-a lovit de următoarea problemă: fiind dat un șir format doar din litere mici ale alfabetului englez, Zedd trebuie să găsească secvențe pe care le poate forma fără ca vreo literă să apară de prea multe ori.

Cerința

Cunoscând textul lui Zedd, să se determine:

Numărul de secvențe distincte în care fiecare literă poate să apară de maximum k ori. Două secvențe sunt considerate distincte dacă diferă fie prin poziția de început, fie prin cea de final.

Cea mai lungă secvență care conține doar litere distincte. Dacă sunt mai multe secvențe de lungime maximă formate din litere distincte se alege prima din punct de vedere lexicografic (alfabetic).

Date de intrare

Fișierul de intrare criptografie.in conține pe prima linie cerința C (care poate fi 1 sau 2), pe linia a doua numărul natural k, cu semnificația de mai sus, precum și un număr natural n, separate printr-un spațiu. Pe a treia linie se află un text format din n litere mici ale alfabetului englez (neseparate prin spații).

Date de ieșire

Fișierul de ieșire criptografie.out va conține pe prima linie:

Dacă C = 1 un număr natural ce reprezintă răspunsul la cerința 1.

Dacă C = 2 șirul ce reprezintă răspunsul la cerința 2.

Restricții și precizări

o secvență este formată dintr-o succesiune de litere aflate pe poziții consecutive într-un șir.

0 < n ≤ 100.000

0 < k ≤ n

Pentru teste în valoare de 67 de puncte C = 1, iar pentru 33 de puncte C = 2

Pentru teste în valoare de 17 puncte se garantează C = 1, k = 1 și n ≤ 100

Pentru teste în valoare de alte 17 puncte se garantează C = 1 și n ≤ 1000

Pentru cerința 2 se garantează că valoarea lui k este 1.

Exemplul 1:

criptografie.in

1

1 4

abac

criptografie.out

8

Explicație

Pentru textul dat, variantele care ar putea fi obținute conform cerinței sunt: a, ab, b, ba, bac, a, ac, c. În total numărul de secvențe cu caractere distincte (k = 1) ce pot fi formate este 8.

Exemplul 2:

criptografie.in

2

1 6

abacba

criptografie.out

acb

Explicație

Lungimea maximă a unei secvențe de elemente distincte este 3. Sunt trei astfel de secvențe. Prima din punct de vedere alfabetic este acb.

Rezolvare

def distinct_sequences_count(k, n, text):

    occurrences = [0] * 26  # Lista pentru a număra aparițiile fiecărei litere

    start = 0  # Poziția de start a secvenței

    distinct_count = 0  # Numărul de secvențe distincte

    for end in range(n):

        char_index = ord(text[end]) - ord('a')

        occurrences[char_index] += 1

        # Menținem numărul de apariții al fiecărei litere sub sau egal cu k

        while max(occurrences) > k:

            occurrences[ord(text[start]) - ord('a')] -= 1

            start += 1

        # Numărăm secvențele distincte și le adăugăm la rezultat

        distinct_count += (end - start + 1)

    return distinct_count

if __name__ == "__main__":

    with open('criptografiein.txt', 'r') as file_in:

        C, k, n = map(int, file_in.readline().split())

        text = file_in.readline().strip()

    result = distinct_sequences_count(k, n, text)

    with open('criptografieout.txt', 'w') as file_out:

        file_out.write(str(result) + '\n')