• Source 
    1.  
    2. #include <bits/stdc++.h>
    3.  
    4. using namespace std;
    5.  
    6. #define int            long long int
    7. #define F              first
    8. #define S              second
    9. #define pb             push_back
    10. #define si             set <int>
    11. #define vi             vector <int>
    12. #define pii            pair <int, int>
    13. #define vpi            vector <pii>
    14. #define vpp            vector <pair<int, pii>>
    15. #define mii            map <int, int>
    16. #define mpi            map <pii, int>
    17. #define spi            set <pii>
    18. #define endl           "\n"
    19. #define sz(x)          ((int) x.size())
    20. #define all(p)         p.begin(), p.end()
    21. #define double         long double
    22. #define que_max        priority_queue <int>
    23. #define que_min        priority_queue <int, vi, greater<int>>
    24. #define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
    25. #define print(a)       for(auto x : a) cout << x << " "; cout << endl
    26. #define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
    27. #define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
    28.  
    29. inline int power(int a, int b)
    30. {
    31.   int x = 1;
    32.   while (b)
    33.   {
    34.     if (b & 1) x *= a;
    35.     a *= a;
    36.     b >>= 1;
    37.   }
    38.   return x;
    39. }
    40.  
    41. template <typename Arg1>
    42. void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
    43. template <typename Arg1, typename... Args>
    44. void __f (const char* names, Arg1&& arg1, Args&&... args)
    45. {
    46.   const char* comma = strchr (names + 1, ',');
    47.   cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
    48. }
    49.  
    50. const int N = 200005;
    51.  
    52.  bool cmp(pair<int,int>a,pair<int,int>b){
    53.      if(a.first==b.first)return a.second<b.second;
    54.      else return a.first>b.first;
    55. }
    56.  
    57. void solve() {
    58.  
    59. string s;
    60. cin>>s;
    61. int odd=0;
    62. int ch=-1;
    63. vector<pair<int,int>>v(26);
    64. for(int i=0; i<26; i++)v[i].second=i;
    65. for(auto c:s){
    66.     v[c-'A'].first++;
    67. }
    68. for(auto i:v)if(i.first%2){odd++;ch=i.second;}
    69. if(odd>1)cout<<"NO SOLUTION"<<endl;
    70. else{
    71.     sort(v.begin(),v.end(),cmp);
    72.     string ans="",anss="";
    73.     // print(v);
    74.     for(int i=0; i<26; i++){
    75.         if(v[i].first%2==0){
    76.             ans+=string(v[i].first/2,('A'+v[i].second));
    77.             // v[i]--;
    78.         }
    79.         else{
    80.             v[i].first--;
    81.             if(v[i].first>0)
    82.             ans+=string(v[i].first/2,('A'+v[i].second));
    83.         }
    84.     }
    85.     for(int i=0; i<26; i++){
    86.         if(v[i].first%2==0){
    87.             anss+=string(v[i].first/2,('A'+v[i].second));
    88.             // v[i]--;
    89.         }
    90.         else{
    91.             if(v[i].first>0)
    92.             anss+=string(v[i].first/2,('A'+v[i].second));
    93.         }
    94.     }
    95.     if(ch!=-1)
    96.     ans+='A'+ch;
    97.     reverse(anss.begin(),anss.end());
    98.     ans+=anss;
    99.     cout<<ans<<endl;
    100. }
    101.  
    102.  
    103.  
    104. }
    105.  
    106. int32_t main()
    107. {
    108.   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    109.  
    110.  
    111.   clock_t z = clock();
    112.  
    113.   int t = 1;
    114. //   cin >> t;
    115.   while (t--) solve();
    116.  
    117.  
    118.  
    119.   return 0;
    120. }
    121.