C. K-Complete Word

 problem Link: Link

code:

Problem Tag: DISJOINT SET UNION(DSU)

1. #include <bits/stdc++.h>
2.  
3. using namespace std;
4.  
5. const int MAXN = 2e5 + 5;
6.  
7. char s[MAXN]; int N, K; int par[MAXN], sz[MAXN], cnt[MAXN][26];
8.  
9. int find(int x) {
10. return par[x] == x ? x : par[x] = find(par[x]);
11. }
12. void Merge(int x, int y) {
13. //if (find(x) != find(y)) par[par[x]] = par[y];
14. int u = find(x);
15. int v = find(y);
16. if(u == v) return;
17. par[u] = v;
18. return;
19. }
20.  
21. int main() {
22. int TT;
23. cin >> TT;
24. while(TT--){
25. cin >> N >> K;
26. cin >> s+1;
27. for (int i = 1; i <= N; i++) par[i] = i, sz[i] = 0, memset(cnt[i], 0, sizeof(cnt[i]));
28. for (int i = 1; i <= N / 2; i++) Merge(i, N - i + 1);
29. for (int i = 1; i <= N - K; i++) Merge(i, i + K);
30. for (int i = 1; i <= N; i++) ++sz[find(i)];
31. for (int i = 1; i <= N; i++) {
32. int F = find(i); ++cnt[F][s[i] - 'a'];
33. }
34. int ans = 0;
35. for (int i = 1; i <= N; i++)
36. if (find(i) == i) {
37. int now = 0;
38. for (int j = 0; j < 26; j++) now = max(now, cnt[i][j]);
39. ans += sz[i] - now;
40. }
41. printf("%d\n", ans);
42. }
43. }
44.