2645 - minlex

Se consideră un cuvânt format numai din litere mici și un număr natural nenul K.

Cerința

Să se determine cuvântul minim lexicografic obținut prin eliminarea a exact K litere din cuvântul inițial.

Date de intrare

Programul citește de la tastatură numărul K, apoi cuvântul.

Date de ieșire

Programul va afișa pe ecran cuvântul rămas după eliminarea a exact K litere, minim lexicografic.

Restricții și precizări

• 3 ≤ lungimea cuvântului ≤ 1.000.000
• Cuvântul este format numai din litere mici ale alfabetului englez.
• 1 ≤ K < lungimea cuvântului
• Literele rămase după eliminare nu-și pot schimba ordinea în cuvânt.

Exemplu:

Intrare

5 zyizxtnfo

Ieșire

info

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

1. Definim funcția care elimină literele

def elimina_litere(k, cuvant):

   # Inițializăm o stivă goală
   stiva = []
   # Parcurgem fiecare literă din cuvânt
   for litera in cuvant:
       # În timp ce mai avem litere de eliminat și stiva nu este goală și ultima literă din stivă este mai mare decât litera curentă
       while k > 0 and stiva and stiva[-1] > litera:
           # Eliminăm ultima literă din stivă
           stiva.pop()
           # Decrementăm numărul de litere care mai trebuie eliminate
           k -= 1
       # Adăugăm litera curentă în stivă
       stiva.append(litera)
   # Dacă mai avem litere de eliminat, le eliminăm de la sfârșitul cuvântului
   while k > 0:
       stiva.pop()
       k -= 1
   # Convertim stiva într-un șir de caractere și îl returnăm
   return .join(stiva)

1. Citim numărul K și cuvântul de la tastatură

intrare = input("Introduceți numărul K și cuvântul, separate printr-un spațiu: ")

1. Despărțim intrarea în K și cuvânt

k, cuvant = intrare.split()

1. Convertim K într-un număr întreg

k = int(k)

1. Apelăm funcția pentru a elimina literele și afișăm rezultatul

print(elimina_litere(k, cuvant))

</syntaxhighlight>