Build Lowest Number by Removing n digits from a given number - GeeksforGeeks

Build Lowest Number by Removing n digits from a given number - GeeksforGeeks

Build Lowest Number by Removing n digits from a given number

Given a string 'str' of digits and an integer 'n', build the lowest possible number by removing 'n' digits from the string and not changing the order of input digits.

Examples:

Input: str = "4325043", n = 3  Output: "2043"    Input: str = "765028321", n = 5  Output: "0221"    Input: str = "121198", n = 2  Output: "1118" 

We strongly recommend to minimize your browser and try this yourself first.
The idea is based on the fact that a character among first (n+1) characters must be there in resultant number. So we pick the smallest of first (n+1) digits and put it in result, and recur for remaining characters. Below is complete algorithm.

Initialize result as empty string       res = ""  buildLowestNumber(str, n, res)  1) If n == 0, then there is nothing to remove.     Append the whole 'str' to 'res' and return    2) Let 'len' be length of 'str'. If 'len' is smaller or equal      to n, then everything can be removed     Append nothing to 'res' and return    3) Find the smallest character among first (n+1) characters     of 'str'.  Let the index of smallest character be minIndex.     Append 'str[minIndex]' to 'res' and recur for substring after     minIndex and for n = n-minIndex         buildLowestNumber(str[minIndex+1..len-1], n-minIndex).

Read full article from Build Lowest Number by Removing n digits from a given number - GeeksforGeeks