How to find the lexicographically smallest string by reversing a substring? : <p>I have a string <code>S</code> which consists of <code>a</code>'s and <code>b</code>'s. Perform the below operation once. Objective is to obtain the lexicographically smallest string.</p>

<p><strong>Operation:</strong>  Reverse exactly one substring of <code>S</code></p>

<p>e.g.</p>

<ol>
<li>if <code>S = abab</code> then <code>Output = aabb</code> (reverse <code>ba</code> of string <code>S</code>)</li>
<li>if <code>S = abba</code> then <code>Output = aabb</code> (reverse <code>bba</code> of string <code>S</code>)</li>
</ol>

<p>My approach</p>

<p><strong>Case 1:</strong> If all characters of the input string are same then output will be the string itself.</p>

<p><strong>Case 2:</strong> if <code>S</code> is of the form <code>aaaaaaa....bbbbbb....</code> then answer will be <code>S</code> itself.</p>

<p><strong>otherwise:</strong> Find the first occurence of <code>b</code> in <code>S</code> say the position is i. String <code>S</code> will look like </p>

<pre><code>aa...bbb...aaaa...bbbb....aaaa....bbbb....aaaaa...
     |
     i   
</code></pre>

<p>In order to obtain the lexicographically smallest string the substring that will be reversed starts from index i. See below for possible ending j.</p>

<pre><code>aa...bbb...aaaa...bbbb....aaaa....bbbb....aaaaa...
     |           |               |               |
     i           j               j               j
</code></pre>

<p>Reverse substring <code>S[i:j]</code> for every j and find the smallest string.
The complexity of the algorithm will be <code>O(|S|*|S|)</code> where <code>|S|</code> is the length of the string.</p>

<p>Is there a better way to solve this problem? Probably <code>O(|S|)</code> solution.</p>

<p>What I am thinking if we can pick the correct <code>j</code> in linear time then we are done. We will pick that j where number of <code>a</code>'s is maximum. If there is one maximum then we solved the problem but what if it's not the case? I have tried a lot. Please help.</p>
