Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define endl '\n'
- #define mp make_pair
- using namespace std;
- typedef long long ll;
- string s;
- const int NMAX = 1e4;
- int parent[NMAX], rnk[NMAX];
- void make_set (int v) {
- parent[v] = v;
- rnk[v] = 0;
- }
- int find_set (int v) {
- if (v == parent[v])
- return v;
- return parent[v] = find_set (parent[v]);
- }
- void union_sets (int a, int b) {
- a = find_set (a);
- b = find_set (b);
- if (a != b) {
- if (rnk[a] < rnk[b])
- swap (a, b);
- parent[b] = a;
- if (rnk[a] == rnk[b])
- ++rnk[a];
- }
- }
- bool used[NMAX];
- int main() {
- #if __APPLE__
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen("tattarrattat.in", "r", stdin);
- freopen("tattarrattat.out", "w", stdout);
- #endif
- cin >> s;
- for (int i = 0; i < s.length(); i++) {
- make_set(i);
- }
- for (int i = 0; i < s.length(); i++) {
- for (int j = 0; j < s.length(); j++) {
- if (s[i] == s[j] && find_set(i) != find_set(j)) {
- union_sets(i, j);
- }
- }
- }
- int n = s.length();
- for (int i = 0; i < (int)s.length() / 2; i++) {
- if (find_set(i) != find_set(n - i - 1)) {
- union_sets(i, n - i - 1);
- }
- }
- int ans = 0;
- for (int i = 0; i < (int)s.length(); ++i){
- if (!used[find_set(i)]) {
- used[find_set(i)] = true;
- int a[27];
- for (int j = 0; j < 27; ++j) {
- a[j] = 0;
- }
- pair<int, char> maxx = {0, 'a'};
- for (int j = 0; j < (int)s.length(); ++j) {
- if (find_set(j) == find_set(i)) {
- a[s[j] - 'a']++;
- if (a[s[j] - 'a'] > maxx.fi) {
- maxx.fi = a[s[j] - 'a'];
- maxx.se = s[j];
- }
- }
- }
- for (int j = 0; j < (int)s.length(); ++j) {
- if (find_set(j) == find_set(i)) {
- if (maxx.se != s[j]) {
- ans++;
- }
- }
- }
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement