No Strings Attached

I have replaced the current char by the max char occuring after it and had a count of (curr - max).Heres the problem link

https://www.codechef.com/JULY18B/problems/NSA

Someone please help me with this problem !!

blackmamba (122)

i have partially accepted solution for both NSA and NMNMX.
if anyone has fully accepted solution of any and wants partial of the other , DM me

@wasp

why are changing with maximum character occuring.

zzzzzzzzaaab

take this example

yes here i change every a to b to the answer is 3

Why are you changing all a's?You can only change 1 letter in the entire string...

I have come up with an O(n^2logn) approach but its still not good enough for 100pts :/

@honeybuzz can you share your algo PM me

@gear how can your solution be O(n) if it is brute force?I think you might be messing up the logic to reduce the complexity and hence are getting WA...Because using brute force to simply calculate the cost of the given string without even making any changes itself is O(n^2).

@vigilante

In abcd
bcd > a so count 3
then cd > b so count 3+2=5
then c>d so count 5+1=6

@Wasp actually my solution is just able to pass 1 test case of the last subtask...Hence even though its better than the brute force(since it passes only 3 cases), my solution passes just 1 more case...Moreover, the 2nd test case of the 2nd subtask still gave TLE...

@honeybuzz

what algo u use for clearing last subtask . how u reduce time complexity..