# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.795312,"math_prob":1.0000066,"size":1792,"snap":"2022-27-2022-33","text_gpt3_token_len":639,"char_repetition_ratio":0.13702461,"word_repetition_ratio":0.0,"special_character_ratio":0.37332588,"punctuation_ratio":0.1525,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000072,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-06-28T00:36:08Z\",\"WARC-Record-ID\":\"<urn:uuid:bf8686c0-e2ee-464e-ac83-7411f0f070b9>\",\"Content-Length\":\"239156\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:bc2c0d55-f23e-412f-a811-7119a267bdb9>\",\"WARC-Concurrent-To\":\"<urn:uuid:5e521cdd-68ea-40ce-8b7c-128b9dc37965>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/151152/maximum-difference-between-maximum-and-minimum-frequency-in-a-subarray/151153\",\"WARC-Payload-Digest\":\"sha1:XPU7QBPFNVDPKWFTXDRTYT5G2NV4VUKQ\",\"WARC-Block-Digest\":\"sha1:ZIXZJZS4WVJ66AOZJXG2JRIOBUASRERM\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656103344783.24_warc_CC-MAIN-20220627225823-20220628015823-00050.warc.gz\"}"}