X
Ask a Question

All Tags

Beautiful unique strings

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".

Nilesh Mishra Aug 23 '2012 at 10:55AM
2
  • anshul Anshul Sep 03 '2012 at 05:23AM

    Can s2 be any string formed from chars of s2 or it has to be a substring?

    Reply
    • nilmish Nilesh Mishra Sep 03 '2012 at 08:22AM

      The new string fromed has to be a substring of the original string

      Reply

Answers: 2

2

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.

Anshul Aug 23 '2012 at 10:55AM

0
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;
   }

}
Rajkumar Singh Aug 23 '2012 at 10:55AM

Answer this Question

You need to login/register to answer the question. Or connect with