Help| Coding | Strings

1

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.

2

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).

3

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
4

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.

5

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…:blush:
Here i will pre calculate the occurrences of all characters of the string.

6

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.

7

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