Beautiful unique strings

2
|
|
viewed: 805 times

A string s is said to be unique if no two characters of s are same. A string s1 is producible from s2 by removing some of the characters from s2. A string s1 is said to be more beautiful than s2 if length of s1 is more than s2 or if both have same length and s1 is lexicographically greater than s2( ex: ba is more beautiful than ab) Input: is a string which can be of maximum 10^6 characters, you have to produce the most beautiful unique string out of the given string.

Sample Input:

babab

Sample Output:

ba

Explanation

In the above test case all unique strings that are producible from s are "ab" and "ba" and "ba" is more beautiful than "ab".

Aug 23 '2012 at 10:55AM
Edited by:
Sachin Gupta

2 Answers

The above problem can be restated as follows: Find the longest substring of a given string which contains all unique chars, in case of a tie return the lexicographically largest.

Linear search algorithm.

void fun(string str)
{
    int pos[256];
    for(int i = 0; i < 256; pos[i++] = -1)
        ;
    string max = "";

    for(int i = 0, j = 0; str[i]; i++)
    {  
        if(pos[ str[i] ] != -1 && j <= pos[ str[i] ])
            j = pos[ str[i] ] + 1;

        pos[ str[i] ] = i;
        int len = i-j+1;
        if(max.size() < len || (max.size() == len && max < str.substr(j, len)))
            max = str.substr(j, len);
    }

    cout << max;
}

I could be wrong, plz point out errors if you find any.

Sep 03 '2012 at 09:45AM

int main(){
    int T;
    cin>>T;
    while(T--){
        char *str = (char*)malloc(sizeof(char*)*Max);
        cin>>str;
        int N = strlen(str);
        vector<char>mystr (N);
        vector<char>::iterator it;

        it = unique_copy(str, str+N,mystr.begin());
        sort(mystr.begin(),it);

        it = unique_copy(mystr.begin(), it, mystr.begin(),myfunction);
        mystr.resize(it-mystr.begin());
        free(str);
        for (int i = mystr.size()-1;i>=0;i--)
        cout<<mystr[i];
        cout << endl;
   }

}
Nov 05 '2012 at 03:12AM

Answer this Question

Please login to answer the question.