title: Beautiful String
body: <p>Got this question from a <a href="http://learn.hackerearth.com/forum/70/beautiful-unique-strings/" rel="nofollow">here</a>. But the runtime of the algorithm which i could figure out was really bad. Here is the question:</p>
  
  <blockquote>
    <p>String s is called unique if all the characters of s are different.
    String s2 is producible from string s1, if we can remove some
    characters of s1 to obtain s2.</p>
    
    <p>String s1 is more beautiful than string s2 if length of s1 is more
    than length of s2 or they have equal length and s1 is
    lexicographically greater than s2.</p>
    
    <p>Given a string s you have to find the most beautiful unique string
    that is producible from s.</p>
    
    <p>Input: First line of input comes a string s having no more than
    1,000,000(10^6) characters. all the characters of s are lowercase
    english letters.</p>
    
    <p>Output: Print the most beautiful unique string that is producable from
    s</p>
    
    <p>Sample Input: babab</p>
    
    <p>Sample Output: ba</p>
  </blockquote>
  
  <p>What i did is this:</p>
  
  <ol>
  <li>Take the string and remove all equal adjacent characters with single one.    Example: input: "bbbbbab" output: "bab", this is the output of this step. Which becomes the input to next steps.</li>
  <li>Now build an array for each unique character in the string. This array will have the indexes of its occurrence in the given input array.</li>
  <li>Note the first occurence of each element. Find min and max of the occurences. Using this iterate over all possible strings which can be formed with words ending at index max. Take the lexicographically greatest.</li>
  <li>Repeat the above by moving max.</li>
  </ol>
  
  <p>I want a correct and efficient algorithm which can scale when the input string is really big.</p>