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

#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++)

    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);