# Editorial : Mr. Pompom and his tricks!

Given a string S, we want to find the lexicographically smallest string A such that:

S ∈ Join(UltaPulta(A), Crazy(A))

Observation 1:

S ∈ Join(UltaPulta(A), Crazy(A))

<==>

UltaPulta(S) ∈ Join(A, Crazy(A))

We know that number of every ‘a’ – ‘z’ is equal to half of S. So we just need to find a smallest A with given number of ‘a’, given number of ‘b’, etc.

So, firstly we find the frequency of every character(can be done easily using Hashing or using dictionary in Python) in given string S. The frequency of the characters in the original string will be exactly half of this frequency.

Now, coming to think about it we have joined the two strings by maintaining the relative order of the characters in both. So our original string will be subsequence of the reverse of the given string(Because we have merged the reverse of the original string). So our aim is to find a lexicographically smallest subsequence in the reverse of the input string S.

Now if we apply brute force and try all the permutations of the string, it would be a very inefficient approach.

Question : So how efficiently can we find the lexicographically smallest substring in a string if we know the frequency of the characters we need?

So we follow the following procedure :             Start traversing each index of the string, check for the frequency of characters we “need” and we “have” (Both stored while counting the frequency of the characters)continously and choose the lexicographically smallest character from the subarray where the frequency of any one character occuring in that subarray increases than what we “need”.

Why? Because whenever any one character’s frequency increases than what we actually need, we will have to compulsorily take one character from that subarray.

For eg. :

Let S = “aegeaggg”

Ultapulta(S) = “gggaegea”

Now as we start traversing we see that at index ‘2’ the frequency of g will exceed(3) than what we need(2). So we, have to necessary take one ‘g’ from that. Next the string will be “ggaegea”. Now applying the same logic we will end up at index ‘4’ where the frequency of again ‘g’ will exceed than what we actually need and so we will take the lexicographically character in that subarray which is ‘a’ and this will be the second character in our answer. Now our string will be “ggegea”. Do this till the length of the string becomes half!

Happy Coding 😀

Solution Code(Python 2.7) :

from collections import defaultdict

answer = [] # This will store our required string.

S = str(raw_input())[::-1]

# Calculate the frequency of each character in the input String S and store it in a dictionary.

InputCount = defaultdict(int)

for c in S:

InputCount[c] += 1

# ‘Original’ will store the values of the frequency of characters needed in the ‘

Original = {}

# The Original frequency of characters is half than the Input string.

for c in InputCount:

Original[c] = InputCount[c] / 2

i = 0

while len(answer) < len(S) / 2:

Lowest_possible_char_index = -1

while True:

c = S[i]

if Original[c] > 0 and (Lowest_possible_char_index < 0 or c < S[Lowest_possible_char_index]):

Lowest_possible_char_index = i

InputCount[c] -= 1

if InputCount[c] < Original[c]:

break

i += 1

# Restore all chars right of the minimum character.

for j in range(Lowest_possible_char_index+1, i+1):

InputCount[S[j]] += 1

Original[S[Lowest_possible_char_index]] -= 1