For ex. if the number is 9511145 if I want to delete 3 least digits from this number the maximum number will be 9545.Deleted digits no need to be contiguous.But digits of the maximum number will remain of their original order. The number can be 10^6 digits long.To solve this problem in iterative approach it could take O(N^2) time.If anyone could suggest any better approach to solve this problem then it would be great help.Thanks in advance.
The solution to this question has been beautifully answered here. Only difference is you have to keep the stack sorted decreasingly.
# process digits from left to right for each digit from left to right if digit <= top of the stack push(digit) continue while (digit > top of the stack) and (we have enough digits to reach n-k digits) pop() push(digit) pop extra digits 9511145 push(9) => 9 push(5) because 5 <= 9 => 95 push(1) because 1 <= 5 => 951 push(1) because 1 <= 1 => 9511 push(1) because 1 <= 1 => 95111 pop() because 4 > 1 and we can still end up with 4 digits => 9511 pop() because 4 > 1 and we can still end up with 4 digits => 951 pop() because 4 > 1 and we can still end up with 4 digits => 95 push(4) because 4 <= 5 => 954 push(5) because we need to have 4 digits at least => 9545