Some Coding Challenges: Extract a minimal possible Number from a String.

The task is to extract from a given string of digits, by removing a fixed number of elements, a sub-string which constitutes the minimal possible integer.

So for instance given 2345421 with an allowed removal count of 4, the minimum number we can obtain is 221.

We can solve this problem by an algorithm that works in O(n) with n being the length of the input string.

A solution written in Java:

var input =  "4345708679702345421";
var k = 4;

var res = new StringBuilder();
while (k > 0 && input.length() > k) {
   var smallestIdx = 0;
   int smallestValue = Integer.parseInt(input, 0, 1, 10);
   var idx = 1;
   while (idx <= k) {
     var value = Integer.parseInt(input, idx, idx + 1, 10);
     if (value < smallestValue) {
       smallestIdx = idx;
       smallestValue = value;
     }
     idx += 1;
   }
   k = k - smallestIdx; // smallestIdx elements have been removed
   res.append(smallestValue);
   input = input.substring(smallestIdx + 1);
}
res.append(input);

System.out.println(res.toString()); // 308679702345421

The idea is to start searching from left to right the smallest digit within the first k+1 digits. The first digit representing this minimum is taken as first digit of our result.

All the digits before this minimum will be removed. That is, if the minimum took place at the index i, then we remove i elements. This leaves us with k-i further elements which we may remove.

We proceed by doing the same but up from index i+1 and with k-i instead of k.

We stop when we have no elements left for removal. The remaining part of the input is then appended to the result.

Thank you for reading!