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.

==Exemplul 1:==

;Intrare

:5 zyizxtnfo

;Ieșire

:Datele de intrare corespund restrictiilor impuse
:info

==Exemplul 2:==

;Intrare

:0

;Ieșire

:Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

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

def validare(litera_k, word):  # functia de validare a datelor de intrare
    if 1 > litera_k or litera_k >= len(word) or len(word) > 1000000:
        raise ValueError
    if not word.islower():
        raise ValueError
    print("Datele de intrare corespund restrictiilor impuse\n")


def elimina_litere(litera_k, word):  # functia de rezolvare
    stiva = []
    for litera in word:
        while litera_k > 0 and stiva and stiva[-1] > litera:
            stiva.pop()
            litera_k -= 1
        stiva.append(litera)
    while litera_k > 0:
        stiva.pop()
        litera_k -= 1
    return ''.join(stiva)


if __name__ == '__main__':
    try:
        k, cuvant = input("Introduceți numărul K și cuvântul, separate printr-un spațiu: ").split()
        k = int(k)
        validare(k, cuvant)
        rezultat = elimina_litere(k, cuvant)
        print(str(rezultat) + '\n')
    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        print("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>