Shared code

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second

int cnt[26];
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s, ans;
	cin >> s;
	for (auto u : s)
		cnt[u - 'A']++;
	int d = count_if(cnt, cnt + 26, [&](int x){ return x&1; });
	if (s.size() & 1 && d == 1){
		for (int i=0; i<26; i++){
			if (cnt[i] & 1 && cnt[i]){
				for (int j=0; j<cnt[i]; j++)
					if (j & 1)
						ans = ans + char(i + 'A');
					else
						ans = char(i + 'A') + ans;
			}
			
		}
		// RACECAR
		for (int i=0; i<26; i++){ 
			if (cnt[i] & 1 ^ 1 && cnt[i]){
				for (int j=0; j<cnt[i]; j++)
					if (j & 1)
						ans = ans + char(i + 'A');
					else
						ans = char(i + 'A') + ans;
			}
		}
	}
	else if (s.size() & 1 ^ 1 && d <= 1){
		for (int i=0; i<26; i++){
			for (int j=0; j<cnt[i]; j++)
				if (j & 1)
					ans = ans + char(i + 'A');
				else
					ans = char(i + 'A') + ans;
			}
		}	
	else 
		ans = "NO SOLUTION";
	cout << ans << '\n';
	return 0;
}