字符串 模拟

3451. 易位构词

DESCRIPTIONSUBMITSTATISTICSDISCUSSION

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

易位构词 (anagram)，指将一个单词中的字母重新排列，原单词中的每个字母都出现有且仅有一次。例如 "unce" 可以被易位构词成 "ecnu"。在某些情况下，要求重排而成的依然是一个单词，但本题没有这种要求，因为我们根本没有词典。

我们所感兴趣的是，有些单词中的字母进行适当的重排后，可以使得构成的单词每个对应的位置上字母都不一样。例如 "unce" 和 "ecnu"，就有 "u" ≠ "e", "n" ≠ "c", "c" ≠ "n", "e" ≠ "u"。现在给出一个单词，问是否存在这样一个重排。

Input

一行一个单词 s (1≤|s|≤105)。单词完全由 26 个小写英文字母构成。

Output

输出一个单词。如果有多解，输出任意解。如果不存在，输出 impossible。

Examples

input

unce

output

ecnu

input

aaaaaa

output

impossible


题目分析 ：
　　当你的一种字母的个数 如果大于 n/2 ， 那么一定是 impossible , 首先 假定 给你的字符串 是有序的，那么你只需要移位最大相同个数即可，然后输出原串对应的字符即可 。

代码示例 ：

char pre[eps];
int pt[30];
char a[eps], b[eps];
vector <char> ve[30];

int main() {

    cin >> pre;
    int len = strlen(pre);
    for(int i = 0; i < len; i++){
        a[i] = pre[i];
    }
    sort(a, a+len);
    for(int i = 0; i < len; i++){
        pt[a[i]-'a']++;
    }
    int maxn = 0;
    for(int i = 0; i < 26; i++){
        if (pt[i] > maxn) maxn = pt[i];
    }
    if (maxn > len/2) {
        printf("impossible
"); 
    } 
    else {
        int p = maxn;
        int k = 0;
        for(int i = len-p; i < len; i++){
            b[k++] = a[i];
        }
        for(int i = 0; i < len - p; i++){
            b[k++] = a[i];
        }
        b[k] = '';
        //cout << b << endl;
        for(int i = 0; i < len; i++){
            ve[a[i]-'a'].push_back(b[i]);
        }
        memset(pt, 0, sizeof(pt));
        //for(int i = 0; i < 26; i++){
            //pt[i] = ve[i].size();    
        //}
        for(int i = 0; i < len; i++){
            int num = pt[pre[i]-'a'];
            printf("%c", ve[pre[i]-'a'][num]);
            pt[pre[i]-'a']++;
        } 
    }
    
    return 0;
}