Find the lexicographical smallest permutation of a string that contains of 'a' and 'b' only such that no. of subsequence of "ab" is x and of "ba" is y

help
,
1

Given a string of ‘a’ and ‘b’ only

for example
string is ‘baaab’ and x=3 and y=3

Find the lexicographical smallest permutation of string that contains

count of sub-sequence ‘ab’ = x times and count of sub-sequence ‘ba’ = y times.

For above example , there is a possible permutation ababa

We can print -1 , in case if its not possible

for example when string is ‘abbb’ and x = 3 and y = 3.

For this example no permutation is possible

What logic will you use ?

4 Likes
2

Approach: First of all, by induction it can prove that the product of count of ‘a’ and count of ‘b’ should be equal to the sum of the count of a subsequence of ‘ab’ and ‘ba’ for any given string. If this does not hold then the answer is ‘Impossible’ else answer always exist.
Now, sort the given string so the count of a subsequence of ‘ba’ becomes zero. Let nx be the count of ‘a’ and ny be count of ‘b’. let a and b be the count of subsequence ‘ab’ and ‘ba’ respectively, then a = nx*ny and b = 0 . Then, from beginning of the string find the ‘a’ which has next ‘b’ to it and swap both untill you reach end of the string. In each swap a is decremented by 1 and b is incremented by 1 . Repeat this until the count of a subsequence of ‘ba’ is achieved i:e a becomes p and b becomes q .


def check(s, p, q):
    global nx ;global ny
    nx=0;ny=0
    for i in range(0, len(s)):
        if s[i] == 'a':
        	nx += 1
        else:
        	ny += 1
    if nx * ny != p + q:
        return 1
    return 0
def smallestPermutation(s, p, q):
    if check(s, p, q) == 1:return "Impossible"
    s = sorted(s)
    a, b, i = nx * ny, 0, 0
    if a == p and b == q:return '' . join(s)
    while True:
        for i in range(0, len(s) - 1):
            if s[i] == 'a' and s[i + 1] == 'b':
                break
        for j in range(i, len(s) - 1):
            if s[j] == 'a' and s[j + 1] == 'b':
                s[j], s[j + 1] = s[j + 1], s[j]
                a -= 1 
                b += 1 
                if a == p and b == q:
                    return '' . join(s)
t=int(input())
for _ in range(t):
    n,p,q=list(map(int,input().split()))
    s=input()
    ans=smallestPermutation(s,p,q)
    if ans=="Impossible":
        print('Impossible')
    else:
        print("Possible")
        print(ans)