### 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