title: Minimum Lexicographical String after K removals of first, second, last or penultimate characters
body: <p><strong>Question:</strong></p>
  <p>Given a string S <code>S.length() &lt;= 5.10^5</code> and an integer K <code>K &lt;= S.length()</code>. For each removal, you can:</p>
  <ul>
  <li>Remove the <strong>first</strong> character of the string</li>
  <li>Remove the <strong>second</strong> character of the string</li>
  <li>Remove the <strong>last</strong> character of the string</li>
  <li>Remove the <strong>second last</strong> character of the string</li>
  </ul>
  <p>How can I do exactly K removals such that the final string has minimum lexicographical order?</p>
  <p><strong>Example:</strong></p>
  <p>S= &quot;abacaaba&quot;, K = 2</p>
  <ul>
  <li>Remove the <strong>second</strong> character of the string</li>
  <li>Remove the <strong>second last</strong> character of the string</li>
  </ul>
  <p>The final string: &quot;aacaaa&quot; which is the smallest lexicographical possible.</p>
  <p><strong>P/S:</strong></p>
  <p>I've tried for many days but can't figure out an efficience way to solve this problem. But I think there's something to do with dynamic programming.</p>