Sort odd indices in ascending order and even indices in descending order of the string

Given a string S, the task is to sort odd indices in ascending order and even indices in descending order of the string.

Examples:

Input: 
S = "Cplusplus"
Output: 
Cululspsp
Explanation:
Sort string S in ascending order: S = "Cululspsp"
Replace odd indices in ascensing order and even indices in
descending order.

Input: 
S = "plusplus"
Output: 
lulupsps

Approach:
Follow the steps below to solve the problem:

• Sort the string in alphabetical order.
• Traverse the string for half-length and at each iteration print ith index and last ith index of the string.
• If the size of the string is odd, after completion of iteration print the middle character of the string.

Below is the implementation of the above approach.

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to sort odd indices in ascending order and even
// indices in descending order of the string
void sortString(string S)
{
    // Length of string
    int n = S.size();

    // Sort string in ascending order
    sort(S.begin(), S.end());

    // Traverse the string
    for (int i = 0; i < n / 2; i++) {
        cout << S[i] << S[n - i - 1];
    }

    // If length of string is odd
    if (n & 1)
        cout << S[n / 2];
}

// Driver Code
int main()
{
    string S = "Cplusplus";
    sortString(S);

    return 0;
}

Output:

Cululspsp

Time Complexity: O(|S| * log|S|)
Auxiliary Space: O(1)