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)