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
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.
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))
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
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
Can someone please tell where I am going wrong. I need only a case where my solution fails.
def update(l, j, k):
for i in range(j , k, -1):
if(i == n - 1):
if(l[j] == 1):
return j
elif(i != n - 1):
if(l[i] - l[i + 1] > 0):
return i
return -1
t = int(input())
while(t > 0):
l = input().split()
n = int(l[0])
p = int(l[1])
ans = ‘’
exp = input()
i = 0
k = 0
index = n
l = [0 for i in range(n)]
sumx = 0
for i in range(n - 1, -1, -1):
if(exp[i] == ‘a’):
sumx += 1
l[i] = sumx
while(i < n):
if(i != n - 1):
a = l[i + 1] - k
else:
a = 0
if(p > 0):
if(a > 0 and index != -1 and p - a != 1):
if(exp[i] == 'b'):
ans += 'a'
p -= 1
index = update(l, index - 1, i)
exp = exp[:i] + 'a' + exp[i + 1 : index] + 'b' + exp[index + 1:]
i += 1
k += 1
else:
ans += 'a'
i += 1
else:
if(exp[i] == 'b'):
if(p >=2):
ans += 'a'
p -= 2
i += 1
else:
ans += exp[i:]
break
else:
ans += 'a'
i += 1
else:
ans = ans + exp[i:]
break
print(ans)
t -= 1
