Maximum difference between maximum and minimum frequency in a subarray

So the problem is given a string, we want to output the substring's length where freqency[c1] - frequency[c2] is MAX. c1 = Most frequent character c2 = Least frequent character

e.g

'aaabbbbbabcbbbaaaa' => 8 ( corresponding to the substring 'bbbbbabcbbb' )

Your problem can be solved in linear time in the length of the input string.

Let $$s=s_1s_2s_3\ldots$$ be your input string. For $$0, let $$n(i,j,c)$$ be the number of occurrences of $$c$$ in $$s_i s_{i+1} \dots s_j$$.

Let $$m^*$$ be the measure of an optimal solution. Now guess the values of $$c_1$$ and $$c_2$$ achieving $$m^*$$ (there are only $$26^2$$ choices) and consider the auxiliary problem of computing two indices $$i(c_1, c_2)$$, $$j(c_1, c_2)$$ that maximize $$n(i(c_1, c_2),j(c_1, c_2),c_1) - n(i(c_1, c_2),j(c_1, c_2),c_2)$$. Let $$m(c_1,c_2)$$ be the value of this maximum.

The auxiliary problem can be solved by noticing that each occurrence of $$c_1$$ in $$s_i s_{i+1} \dots s_j$$ contributes $$1$$ to the above quantity while each occurrence of $$c_2$$ contributes $$-1$$ (other characters contribute $$0$$). Then, this auxiliary problem is equivalent to the maximum subarray problem, which can be easily solved in time $$O(|s|)$$.

Among all guesses, pick the one maximizing $$m(c_1, c_2)$$ and return $$j(c_1, c_2) - i(c_1, c_2) + 1$$.

To see that this algorithm is correct, consider any guess $$c_1, c_2$$ and let $$i=i(c_1, c_2)$$ and $$j=j(c_1, c_2)$$. Notice that if we choose $$c^*_1$$ and $$c^*_2$$ as (one of) the most and least frequent characters in $$s_i, \dots, s_j$$, we must have $$m^* \ge n(i, j, c_1^*) - n(i, j, c_2^*) \ge n(i, j, c_1) - n(i, j, c_2) = m(c_1,c_2)$$. In other words, $$m(c_1,c_2)$$ is always a lower bound to $$m^*$$.

Consider now the case in which your guess of $$c_1$$ and $$c_2$$ was correct (i.e., $$c_1$$ and $$c_2$$ are the most and less frequent occurring characters in an optimal solution, respectively). Since the optimal substring induces a feasible contiguous subarray for the auxiliary problem with measure $$m^*$$, we must have $$m(c_1, c_2) \ge m^*$$, thus implying $$m(c_1, c_2)=m^*$$.

We can provide an $$O(n)$$ algorithm for such a problem

For every pair of characters $$(c_1,c_2)$$, we take the input string, ignore all other characters, replace $$c_1$$ by $$1$$, replace $$c_2$$ by $$-1$$ and then compute the largest sum of a contiguous subarray, which will be the deviation ($$f_{max} - f{min}$$) for this pair

There are only $$26 \times 26$$ such pairs (which is a constant), an each pair uses only $$O(n)$$ time, so we end up with $$O(n)$$ time algorithm

Lets take an example so this becomes clear

Let the input string be $$aaabbbbbabcbbbaaaa$$

Now for example, let $$c_1 = b, c_2 = a$$

Ignore every other character (or simply replace it by $$0$$), then replace $$b$$ by $$1$$ and $$a$$ by $$-1$$, then we get the array $$-1 \ -1 \ -1 \ 1 \ 1 \ 1 \ 1 \ 1 \ -1 \ 1 \ 1 \ 1 \ 1 \ -1 \ -1 \ -1 \ -1$$, now compute the maximum sum of a contiguous subarray = $$8$$

And so $$c_1 = b, c_2 = a$$ we have $$f_{max} - f_{min} = 8$$ ($$c_1$$ is max and $$c_2$$ is min)

Now repeat this for every pair $$c_1,c_2$$, and the output would be the pair with the greatest deviation ($$f_{max} - f_{min}$$)

Again, there are only $$26 \times 26$$ such pairs (constant), and for every pair we need only $$O(n)$$ steps, and getting the max over a constant number of pairs takes constant time, so we end up with an $$O(n)$$ algorithm

• The approach is correct but it will not give the right answer. While calculating the maximum sub array sum, we should take only those subarrays which have at least one -1 in it. Segment with all +1s is equivalent to substrings with only a single character. Count of such segments are incorrect. e.g. abb ==> -1,1,1, the ans should be 1 not 2. We cant take the segment "bb" (i.e. [1,1]). One interesting fact here is, if string has only one character then the ans should be 0 not the length of the string. i.e. aaa => 1,1,1 = 0 NOT 3. Jun 4 at 23:11