Given a string find max deviation of the string.

Deviation means the difference between

Max occuring char - min occuring char.

Ex - bbacccababa

Ans - ccca with max dev as 2

n <=10^4

Not able to come up with an efficient approach. Please help.

Given a string find max deviation of the string.

Deviation means the difference between

Max occuring char - min occuring char.

Ex - bbacccababa

Ans - ccca with max dev as 2

n <=10^4

Not able to come up with an efficient approach. Please help.

Your question is not clear. Do we have to find the max deviation among all substrings of the given string (I am assuming it for now) ?

Let us assume that the given string is S of length n. Suppose we randomly picked a pair of distinct characters x, y \in [a-z]. We can find the maximum value of frequency (x) - frequency (y) over all the substrings of S in O (n). Let us call this maximum value mvalue (S, x, y).

Observe that max of mvalue (S, x, y) over all distinct x, y will give us our answer. So, we have ourselves a solution of order 26 * 26 * n.

I know I have not explained in detail. Let me know if you have any further doubts (there are no silly doubts, we understand or we donât).

Thanks I got ur point @pandey_adm Really thanks for the effort in answering and sorry for a very late Thanksđ.

Also just one doubt - we will do the sliding window to get max dev for x,y correct?.

1 Like

You donât have to thank me, helping each other is what we do in communities.

I am assuming by this

You mean calculating mvalue (S, x, y). Suppose we make a corresponding array A of length n defined as

A[i] = \begin{cases} 1, & A[i] = x \\ -1, & A[i] = y \\ 0, & otherwise \end{cases}

Note that we need to find l, r \in [n] such that \sum_{i = l}^{r} A[i] is maximum. That is not all though, we need to make sure that both 1 and -1 do occur in that range A[l, r]. This is a good problem in itself. See if this helps.

Please elaborate on your solution (show no fear). I need to know exactly what you have in mind when you say âsliding windowâ, as it is just a technique.

By sliding window

My idea was we will take 2 pointers i=0,j=n-1 now we will find the mvalue(s,x,y) by contracting the string according based on if we encouter x,y or something else and will keep on updating the max value received.

This is what i am thinkingâŚ

Here i will pre calculate the occurrences of all characters of the string.

I donât think just contracting would be optimal. I highly recommend coding it up and submitting. Please reply back with the submission link, regardless of the verdict.

@vraj1994 Could you share your approach to the problem? I tried the solution and I ended up with TLE