Gui B.L Software Engineering-Code and posts about tech and programming

Find lowest possible sequential number from numeric string while deleting k elements

19 March 2015

Problem overview

Given a numeric string S (i.e "6205123" ) of size N containing only digits and a number K where 1 <= K <= N, find the minimum number of possible from deleting K elements in the string while preserving the original digits orders.

Algorithm analysis

Convert the string to integer array, create an auxiliary array in order to store the indexes which will be part of the final solution.
Pick lowest number possible from index i where 0 <= i < (N - k)
Since we need to preserve the order of elements use sliding window mechanism to keep track of the minimun number in range and remnant numbers to keep.

Code in Java

Below is the code that depicts the idea above:

public static String findLowestPossibleNumberFromNumericString(String s, int n) {
if (n <= 0 || s == null || s.length() == 0 || n > s.length()) {
        return null;        

    }

<span class="k">if</span> <span class="o">(</span><span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">()</span> <span class="o">==</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">return</span> <span class="n">s</span><span class="o">;</span>
<span class="o">}</span>

<span class="kt">int</span><span class="o">[]</span> <span class="n">indexKeep</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">()];</span>
<span class="kt">int</span><span class="o">[]</span> <span class="n">numbers</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">()];</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">();</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">numbers</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">Integer</span><span class="o">.</span><span class="na">parseInt</span><span class="o">(</span><span class="n">s</span><span class="o">.</span><span class="na">substring</span><span class="o">(</span><span class="n">i</span><span class="o">,</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="o">));</span>
    <span class="n">indexKeep</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="o">}</span>

<span class="kt">int</span> <span class="n">localMin</span> <span class="o">=</span> <span class="n">Integer</span><span class="o">.</span><span class="na">MAX_VALUE</span><span class="o">;</span>
<span class="kt">int</span> <span class="n">localMinIndex</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="kt">int</span> <span class="n">indexStart</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>        
<span class="kt">int</span> <span class="n">totalCharsToKeep</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">()</span> <span class="o">-</span> <span class="n">n</span><span class="o">;</span>
<span class="kt">int</span> <span class="n">indexEnd</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">()</span> <span class="o">-</span> <span class="n">totalCharsToKeep</span><span class="o">;</span>
<span class="k">while</span> <span class="o">(</span><span class="n">totalCharsToKeep</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">indexStart</span> <span class="o">&lt;</span> <span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">())</span> <span class="o">{</span>            
    <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">indexStart</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">indexEnd</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>             
        <span class="k">if</span> <span class="o">(</span><span class="n">localMin</span> <span class="o">&gt;</span> <span class="n">numbers</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
            <span class="n">localMin</span> <span class="o">=</span> <span class="n">numbers</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>
            <span class="n">localMinIndex</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span>              
        <span class="o">}</span>
    <span class="o">}</span>                        
    <span class="n">indexKeep</span><span class="o">[</span><span class="n">localMinIndex</span><span class="o">]</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
    <span class="n">totalCharsToKeep</span><span class="o">--;</span>
    <span class="n">indexStart</span> <span class="o">=</span> <span class="n">localMinIndex</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span>
    <span class="n">indexEnd</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="na">length</span><span class="o">()</span> <span class="o">-</span> <span class="n">totalCharsToKeep</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span>
    <span class="n">localMin</span> <span class="o">=</span> <span class="n">Integer</span><span class="o">.</span><span class="na">MAX_VALUE</span><span class="o">;</span>
<span class="o">}</span>

<span class="n">StringBuilder</span> <span class="n">sb</span> <span class="o">=</span> <span class="k">new</span> <span class="n">StringBuilder</span><span class="o">();</span>

<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">indexKeep</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">indexKeep</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">==</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">sb</span><span class="o">.</span><span class="na">append</span><span class="o">(</span><span class="n">numbers</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span>
    <span class="o">}</span>            
<span class="o">}</span>

<span class="k">return</span> <span class="n">sb</span><span class="o">.</span><span class="na">toString</span><span class="o">();</span>


}

Full source code