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

<syntaxhighlight lang="python" line>

1. 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

1. 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.")

</syntaxhighlight>