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

Smallest restricted palindrome.cpp
content_copyfile_download
//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);
}