#include<stdio.h> #include<string.h> #define MAX_LEN 1002 int partition(char string[], int low, int high) { char pivot = string[high]; int i = low  1; int j; for (j = low; j <= high  1; j++) { if (string[j] >= pivot) { i++; char temp = string[j]; string[j] = string[i]; string[i] = temp; } } char temp = string[i + 1]; string[i + 1] = string[high]; string[high] = temp; return (i + 1); } void quickSort(char string[], int low, int high) { if (low < high) { int point = partition(string, low, high); quickSort(string, low, point  1); quickSort(string, point + 1, high); } } int main() { int testCase; scanf("%d", &testCase); int t; for (t = 0; t < testCase; t++) { char string[MAX_LEN]; scanf("%s", string); quickSort(string, 0, strlen(string)  1); //Printing Result... char result[strlen(string)]; int mid = strlen(string) / 2; int low = mid  1; int high = mid + 1; int pointer = 0; result[mid] = string[pointer++]; while (high < strlen(string) && low >= 0) { result[high++] = string[pointer++]; result[low] = string[pointer++]; } int i; for (i = 0; i < strlen(string); i++) { printf("%c", result[i]); } printf("\n"); } return 0; }
Problem Description
Trico is trying to impress a girl. But the girl is not showing any sign of interest to him. So his best friend suggested him to gift one Grovyle string to her. Grovlye string is a odd length string consisting of only lowercase alphabets arranged in such a way that a number X associated with it is smallest as possible.
X is calculated as : First take absolute distance of each character’s position from the center of the string i.e., (string length/2) and then multiply the distance with its ASCII value. Similarly find all the values and add them.
Example : Given string : aaa
Here only one unique permutation is possible : aaa
distances are : for first a, d1 = 1, second a, d2 =0, third a, d3 = 1;
so X = 1 X 97 + 0 X 97 + 1 X 97 = 194;
So given a string of odd length consisting of only lowercase alphabets, find one permutation of the given string such that X is smallest as possible. And if there are many such strings then print the lexicographically smallest one.
Input: First line contains T, the number of test cases that follow. Next T lines, each contains one odd length string consisting of only lowercase alphabets.
Output: For each test case, print the desired result in separate lines.
Constraints:
1 <= T <= 1000
0 <= String Length <= 1001

Test Case 1
Input (stdin)
2 aaa abc
Expected Output
aaa acb

Test Case 2
Input (stdin)
3 aaa abc ccb
Expected Output
aaa acb bcc