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 les; lungime sir ⩽ 10000

Exemplu

Intrare

aadcaabcbacadca

Ieșire

5

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> def lungime_minima(s):

   # Creăm un set pentru a stoca toate literele unice din șir
   litere_unice = set(s)
   # Inițializăm lungimea minimă cu lungimea șirului
   lungime_min = len(s)
   # Parcurgem șirul cu o fereastră de caractere
   for i in range(len(s)):
       for j in range(i, len(s)):
           # Dacă fereastra conține toate literele unice, actualizăm lungimea minimă
           if set(s[i:j+1]) == litere_unice:
               lungime_min = min(lungime_min, j-i+1)
   
   # Returnăm lungimea minimă
   return lungime_min

s = input() print(lungime_minima(s))

</syntaxhighlight>