Remove K digits to find the smallest number

remove_k_digits_to_form_the_smallest_number.py

"""
https://scammingthecodinginterview.com
Week 3: Greedy
Problem: 3
"""

class Solution(object):

    def solve(self, a, k):
        out = []
        for num in a:
            while k and out and out[-1] > num:
                out.pop()
                k -= 1
            out.append(num)
        return ''.join(out[:-k or None]).lstrip('0') or '0'


if __name__ == "__main__":
    a = "1432219"
    k = 3
    ans = Solution().solve(a, k)
    print(ans)