Question : Given a String (Eg:aabbbbaa), for all the substrings find the difference between freq[c1] — freq[c2] where c1 is the maximum occurring character and c2 is the minimum occurring character of that substring and print the largest difference of all substring of the string.
if u didn't get the question the link is below : https://leetcode.com/problems/substring-with-largest-variance/
I saw many of the solutions but couldn't understand the main intuition of applying the kadane Algo.
any other approach or kadane approach ,can anyone explain !!!
Having an input string we do not know which characters $$$c1$$$ and $$$c2$$$ are. But we can try all possible pairs $$$(c1,c2)$$$ assuming that $$$freq[c1] \ge freq[c2]$$$. For the choosed characters $$$c1$$$ and $$$c2$$$ we can transform the initial string to the array of the same size by applying the following rules:
So now we have the array consisting of $$$-1$$$, $$$0$$$ and $$$1$$$ with the property that the difference between $$$freq[c1] — freq[c2]$$$ on substring is simply the sum of all array elements on the corresponding subarray. Thus our problem becomes Maximum subarray problem which can be solved by Kadane algorithm.
Another important observation why this works, because, the problem of finding any two characters $$$c1,c2$$$ such that $$$max(|f[c1]-f[c2]|)$$$ is maximized over all substrings among all pairs of characters $$$c1,c2$$$ is equivalent to the above problem which OP asked.
If you compress the string (skip zeroes), then you can get complexity n * A instead of n * A^2. In fact this is a problem from 18th POI.