-
Notifications
You must be signed in to change notification settings - Fork 17
/
Min Adj Swaps to Make Palindrome
61 lines (51 loc) · 1.34 KB
/
Min Adj Swaps to Make Palindrome
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<vector>
using namespace std;
int main() {
int T; cin >> T;
string s;
for(; T > 0 ; T--){
cin >> s;
vector<int> cc(26,0);
for(char c : s)
cc[c-'a']++;
int occured = 0;
for(int i = 0 ; i < 26 ; i++)
occured += (cc[i] & 1);
// more than one element occured odd no. of times
if(occured > 1){
cout << -1 << endl;
continue;
}
// core begins
int end = s.length()-1, ans = 0;
for(int i = 0 ; i < s.length()/2 ; i++){
if(s[i]==s[end-i])
continue;
// proceed if ends are not same
int j, k;
for(j = i+1 ; j <= end-i && s[j]!=s[end-i] ; j++);
for(k = end-i-1; k >= i && s[k]!=s[i] ; k--);
// choose minimum distance
ans += min(j-i, end-i-k);
if( j-i < end-i-k){
for(int p = j; p > i ; p--)
swap(s[p], s[p-1]);
}else{
for(int p = k ; p < end-i ; p++)
swap(s[p], s[p+1]);
}
}
// core end
cout << ans << endl;
}
}
/*
6
admma
adamm
daamm
mamad
asflkj
aabb
*/