CBA Subsequence

Easy

Given a string, rearrange it in such a way that it has no subsequence as cba. If there are multiple answers return the lexicographically smallest one.

Example 1:

Input:
N=6
S="aaaaab"

Output:
aaaaab

Explanation: "aaaaab" has no subsequence as cba and is 
lexicographically the smallest one.

Example 2:

Input: 
N=3 
S="cba"

Output: 
abc.

Explanation: "abc" has no subsequence as cba and is
lexicographically the smallest one.

 

Your Task:
You don't need to read input or print anything. Your task is to complete the function cbaSubsequence() which takes the string S, its size N as input parameters and returns the rearranged string.

 

Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(1)

 

Constraints:
1<=N<=10⁵
S contains only lowercase English alphabets.