0
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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^*$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jun 4 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.