TOPALIN - Palindrome String
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
char s[100010];
int n, res, total, cmax;
int C[300], a[300][300], vs[300];
void dfs(int i) {
vs[i] = true;
total += C[i];
cmax = max( cmax, C[i]);
for(int j=0;j<300;++j)
if(!vs[j] && a[i][j]) dfs(j);
}
int main() {
gets(s);
n = strlen(s);
//printf("%d\n", n);
for(int i=0;i<n;++i) C[s[i]]++;
for(int i=0,j=n-1;i<j;++i,--j) a[s[i]][s[j]] = a[s[j]][s[i]] = 1;
for(int i=0;i<300;++i)
if(!vs[i]) {
total = cmax = 0;
dfs(i);
res += total - cmax;
}
// cout << res << endl;
printf("%d\n", res);
return 0;
}