Construct smallest number after removing k digits from a string
Given the string representation of a non-negative integer and an integer k, find the smallest number that remains after taking out k digits from it. Assume that the string contains atleast k digits.
For example,
Output: 2429
Explanation: We can obtain the smallest number, 2429, by removing two digits (8 and 7) from 284729.
Input: str = 101, k = 1
Output: 1
Explanation: Remove the first one to form the smallest number 1.
There is a simple rule to get the smallest number possible by removing a single digit from it: process the digits from left to right and remove the first digit that is greater than its subsequent digit. We can easily extend this solution for k digits by repeating this process k times. However, the time complexity of this approach is O(n2).
We can reduce the time complexity to linear by using the stack to store the possible candidates up until the present position. The idea is to iterate over the string from left to right and maintain a stack data structure. If the current digit is less than the top digit of the stack, repeatedly remove digits from the stack until the current digit becomes greater than the top element. Then push the current digit to the stack only if it doesn’t result in any leading zeros. Once the k pop operations on the stack have been completed, insert the remaining digits into the stack. If k pop operations have not been done on the stack at the end of the iteration, remove the excess digits from the top of the stack. Finally, construct a new string from the stack’s elements, from bottom to top.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <string> using namespace std; string removeDigits(string const &str, int k) { // base case if (k >= str.size()) { return "0"; } // take string as a substitute for stack string stack; // iterate over the string for (auto &c: str) { // if the last digit of the stack is more than the current digit while (!stack.empty() && stack.back() > c && k > 0) { // remove the last digit and decrement k stack.pop_back(); k--; } // push the current digit to the stack if it doesn't result in any leading zeros if (!(stack.empty() && c == '0')) { stack.push_back(c); } } // remove the remaining digits from the stack while (!stack.empty() && k > 0) { stack.pop_back(); k--; } return stack.empty() ? "0" : stack; } int main() { string str = "284729"; int k = 2; cout << removeDigits(str, k); return 0; } |
Output:
2429
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
import java.util.Stack; class Main { public static String removeDigits(String str, int k) { // base case if (k >= str.length()) { return "0"; } // take stack Stack<Character> stack = new Stack<>(); // iterate over the string for (char c: str.toCharArray()) { // if the last digit of the stack is more than the current digit while (!stack.isEmpty() && stack.peek() > c && k > 0) { // remove the last digit and decrement k stack.pop(); k--; } // push the current digit to the stack if it doesn't result // in any leading zeros if (!(stack.empty() && c == '0')) { stack.push(c); } } // remove the remaining digits from the stack while (!stack.empty() && k > 0) { stack.pop(); k--; } StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { sb.append(stack.pop()); } String result = sb.reverse().toString(); return result.isEmpty() ? "0": result; } public static void main(String[] args) { String str = "284729"; int k = 2; System.out.println(removeDigits(str, k)); } } |
Output:
2429
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
from collections import deque def removeDigits(s, k): # base case if k >= len(s): return '0' # take stack stack = deque() # iterate over the string for c in s: # if the last digit of the stack is more than the current digit while len(stack) > 0 and stack[-1] > c and k > 0: # remove the last digit and decrement k stack.pop() k = k - 1 # push the current digit to the stack if it doesn't result in any leading zeros if len(stack) or c != '0': stack.append(c) # remove the remaining digits from the stack while stack and k > 0: stack.pop() k = k - 1 return ''.join(stack) if stack else '0' if __name__ == '__main__': s = '284729' k = 2 print(removeDigits(s, k)) |
Output:
2429
The time complexity of the above solution is O(n) and requires O(n) additional space for the stack data structure, where n is the number of digits.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)