CBA Subsequence solution

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<=105
S contains only lowercase English alphabets.

 Solution

Click here

Leave a Comment