BANSTR editorial Enigma

PROBLEM LINK:

BANSTR - Banana String

Author - kabeer27

DIFFICULTY:

Medium

PREREQUISITES:

Greedy, Binary Search

PROBLEM:

Given a string consisting of 'a' & 'b' and P points, find the lexicographically smallest string that you can make if each swap in the string costs 1 point and each replacement costs 2 point.

Explanation

Approach 1:

First we make a pre computed array called count_{a}[i] will represent the number of a's on the right side of i^{th} index in input string (excluding i^{th}).

Similarly a prefix array to maintain count of b's till i^{th} index (including i^{th}).

We can perform binary search on index, here index will represent the position till which where we can make all characters 'a' continuously.

Now at any index it is more beneficial to have more replacements than swaps, as more the replacements the more a's in the string after the index till where we made all characters 'a'.

To count the number of replacements we can just run a linear loop and check if x replacements and count_b - x swaps are within cost and this many swaps are available using the count_a array.

This way we can find the highest index till where we can get continuous a's.

Approach 2:

Count total b's in the string and initialize a count for a's with 0.

We can convert the above solution to be linear, if we start iterating from the right hand side at every i^{th} index we can check if it is possible to make all a's till that index by checking if

min(count_a, points) + remaining ~ points/2 >= count_b

As soon as this if condition is true we can break off the loop,

Now using a linear loop which we used in approach 1 we maximize the number of replacements.

Note: All swaps should be done starting from the rear end to get smallest string

Author solution

Author Solution

I also had a greedy approach. I swapped all rightmost a with leftmost b within possible input and marked indices swapped. Then ran a linear search and visited b costs 1 and other b costs 2 and find the answer.

My code

3 Likes

Can someone please help me where am I going wrong

for _ in range(int(input())):
    n,p = map(int,input().split())
    s = list(input())
    t = n-1
    x = n
    flag = True
    for i in range(n):
        if s[i]=='a':
            continue
        for j in range(t,i,-1):
            if s[j]=='a' and p>0:
                s[i],s[j] = s[j],s[i]
                x = j-1
                p -= 1
                if j==i+1:
                    flag = False
                break
            if j==i+1:
                flag = False
        t = x
        if not flag:
            for k in range(j-1,n):
                if p>1:
                    if s[k] != 'a':
                        s[k] = 'a'
                        p -=2
                else:
                    break
            break
    print(''.join(s))

@l_returns or @vijju123 or someone please help on my above query.

please somebody explain me this approaches with an example

Consider the testcase:

1
1 2
b

2 Likes

I have tried with this also and tried all the following cases, will you please or anyone help me with the corner cases for which the code(click here) can give the wrong answer :

I am thinking the following outputs are meeting the expected output, please correct me if that’s wrong.
—Tried TCs :–
9
1 1
b
2 2
bb
1 3
b
14 3
ababababababab
3 2
bab
5 3
bbbba
17 7
abaabbbbbbbbababa
10 5
bbbbbbbbbb
10 1
abaaaabaaa

—OutPut :–
b
ab
a
aaaaaaabbbbbbb
abb
aabbb
aaaaaaaabbbbbbbbb
aabbbbbbbb
aaaaaabaab

Your output is wrong for test case
3 2
bab
Output should be
aab

2 Likes

Thank you so much @kabeer27 and @ssjgz, tried with following TCs as well and finally got AC Solution, My previous logic was giving wrong answer for the following cases. Running behind this problem since 2 days to know where am I going wrong. Thank you for help :hugs:

—TCs:–
5
21 2
abbbaaaaabaaaaabaaaab
21 11
abbbaaaaabaaaaabaaaab
3 2
bab
5 2
bbaab
5 3
bbaab

—OutPut :–
aaabaaaaabaaaaabaabbb
aaaaaaaaaaaaaaaaaaaab
aab
aabbb
aaabb

2 Likes