Can anyone help me with the better solution O(n^3) for this Problem ?

Revision en1, by itrator, 2022-07-21 17:02:56

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 !!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English itrator 2022-07-21 17:02:56 666 Initial revision (published)