codeforce 600C - Make Palindrome

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include<deque>
 7 #include<vector>
 8 using namespace std;
 9 const double eps = 1e-8;
10 const double PI = acos(-1.0);
11 const int maxn=200010;
12 string st;
13 int cnt[maxn];
14 deque<char> qu;
15 vector<int> odd;
16 
17 int main()
18 {
19     cin>>st;
20     memset(cnt,0,sizeof(cnt[0]));
21     for(int i=0; i<st.size(); i++)
22     {
23         cnt[st[i]]++;
24     }
25     for(int i=‘a‘; i<=‘z‘; i++)
26     {
27         if(cnt[i]%2)
28             odd.push_back(i);
29     }
30     sort(odd.begin(),odd.end());
31     int l=0;
32     int r=odd.size()-1;
33     while(l<r)
34     {
35         cnt[odd[l]]++;
36         cnt[odd[r]]--;
37         l++;
38         r--;
39     }
40     for(int i=‘a‘; i<=‘z‘; i++)
41     {
42         if(cnt[i]%2)
43         {
44             cnt[i]--;
45             qu.push_back(i);
46             break;
47         }
48     }
49     for(int i=‘z‘; i>=‘a‘; i--)
50     {
51         while(cnt[i])
52         {
53             qu.push_back(i);
54             qu.push_front(i);
55             cnt[i]-=2;
56         }
57     }
58     while(qu.size())
59     {
60         cout<<qu.front();
61         qu.pop_front();
62     }
63     cout<<endl;
64     return 0;
65 }