2132 - Min Subsir

Se consideră un șir de caractere format din litere mici ale alfabetului englez.

Cerinţa

Să se determine lungimea minimă a unei secvențe care conține toate literele întâlnite în șirul inițial.

Date de intrare

Programul citește de la tastatură șirul de caractere.

Date de ieşire

Programul va afișa pe ecran lungimea secvențele cerute.

Restricții și precizări

• 1 ⩽ lungime sir ⩽ 10000

Exemplul 1

Intrare

aadcaabcbacadca

Ieșire

Datele introduse corespund restricțiilor impuse.

5

Exemplul 2

Intrare

54454534

Ieșire

Datele introduse nu corespund restricțiilor impuse.

Explicație

Sunt folosite literele: a,b,c,d.

Secvențe de lungime minimă care folosesc toate literele: dcaab, bacad.

Rezolvare

# 2132 -Min Subsir
def verificare(verif_car):
    # Verificăm dacă lungimea șirului este în intervalul [1, 10000]
    if 1 <= len(verif_car) <= 10000:
        # Verificăm dacă șirul conține doar litere mici ale alfabetului englez
        if not all(c.islower() for c in verif_car if not c.isspace()):
            # Dacă șirul conține alte caractere, ridicăm o excepție
            raise ValueError
        # Dacă șirul este valid, îl returnăm
        return verif_car
    else:
        # Dacă șirul nu este valid, ridicăm o excepție
        raise ValueError


# Funcția lungime_minima determină lungimea minim
def lungime_minima(min_lung):
    litere_unice = set(min_lung)
    lungime_min = len(min_lung)
    for i in range(len(min_lung)):
        for j in range(i, len(min_lung)):
            if set(min_lung[i:j+1]) == litere_unice:
                lungime_min = min(lungime_min, j-i+1)
    return lungime_min


if __name__ == "__main__":
    try:
        # Citim șirul de la utilizator
        s = input("Introduceti sirul de caractere: ")
        # Validăm șirul
        s = verificare(s)
        print("Datele introduse corespund restricțiilor impuse.")
        print(lungime_minima(s))
    except ValueError:
        # Dacă șirul nu este valid, afișăm un mesaj de eroare
        print("Datele introduse nu corespund restricțiilor impuse.")