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

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