ronith
10/25/2018 - 8:47 AM

## Smallest restricted palindrome

Given a string, s consisting of n lowercase English letters, construct another string, t. such that contains only letters s (each letter can be used at most the number of times it appears in ). String tsa palindrome, t is the longest possible, and if there are still many such strings then is the lexicographically smallest among them.

Constraints: 1<=n<= 10^5

``````//https://lh6.googleusercontent.com/hakVMv-9iun3Lyce1kZaC51CVB69RAK7Xr0CSz39kOHhfvkzYZZOjfaOo6CW9c5iJKX7B8lBp8Eb_826RwtQCov-_RdKp6iKN-lS4VfJY0S-F_qrnI8ZB69IMYDAsRZNKcZk4875
#include <bits/stdc++.h>
using namespace std;

string func(string s) {
map <char, int> m;
int n=s.length();
for (int i=0;i<n;i++)
m[s[i]]++;

string str= "";
char mini= 'z';
map <char, int> ::iterator i;

for (i= m.begin(); i!= m.end(); ++i)
cout<< i->first << " "<< i->second<< "\n";

for (i= m.begin(); i!= m.end(); ++i) {
if (i->second == 1)
mini= min(i->first, mini);

else {
while (i->second > 1) {
str+= i->first;
i->second-= 2;
}
if (i->second == 1)
mini= min(i->first, mini);
}
}
s= str+mini;
reverse(str.begin(), str.end());
s+= str;
return s;
}

int main() {
string s;
getline(cin, s);

cout<<func(s);
}
``````