Editing 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">

# 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)

# 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: ")
# Despărțim intrarea în K și cuvânt
k, cuvant = intrare.split()
# Convertim K într-un număr întreg
k = int(k)
# Apelăm funcția pentru a elimina literele și afișăm rezultatul
print(elimina_litere(k, cuvant))

</syntaxhighlight>