Maximum difference between maximum and minimum frequency in a subarray

Question

Can anyone please help me with a better solution than O(n^3) for this problem?

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

Also please help if there's similar set of problem.

Answer 1

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<i\le j \le |s|$, 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^*$.

Answer 2

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