Shared code

#include<bits/stdc++.h>
#define ll long long
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
 
int main(){
	fio;
	string s; cin>>s;
	map<char,int> lks;
	for(char x: s) lks[x]+=1;
	if((s.length()&1)){
		bool flag=true;
		int count=0;
		for(auto x : lks){
			if((x.second&1)) count+=1;
			if(count==2){
				flag=false; break;
			}
		}
		if(flag){
			string ans="";
			for(auto &x : lks){
				if((x.second&1)){
					ans+=x.first;
					x.second-=1;
				}
			}
			for(auto x : lks){
				ans=ans + string(x.second/2,x.first);
				ans=string(x.second/2,x.first) + ans;
			}
			cout<<ans<<"\n";
		}
		else cout<<"NO SOLUTION\n";
	}
	else{
		int count=0; bool flag=true;
		for(auto x : lks){
			if((x.second&1)) count+=1;
			if(count==1){
				flag=false; break;
			}
		}
		if(flag){
			string ans="";
			for(auto x : lks){
				ans=ans + string(x.second/2,x.first);
				ans=string(x.second/2,x.first) + ans;
			}
			cout<<ans<<"\n";
		}
		else cout<<"NO SOLUTION\n";
		
	}
 
	return 0;
}