Find maximum deviation of all substrings

Question

Given a string, find the maximum deviation among all substrings. The maximum deviation is defined as the difference between the maximum frequency of a character and the minimum frequency of a character.

For example, in abcaba, a has a frequency of 3; b has a frequency of 2; c has a frequency of 1. so a has the maximum frequency, which is 3, whereas c has a minimum frequency of 1. Therefore the deviation of this string is 3 - 1 = 2. And we also need to find all other deviations for each of the substrings for abacaba, the maximum among them is the answer.

I couldn't think of a better way rather than the obvious brute force approach. Thanks in advance!

Answer 1

For finding all substrings you have to consider O(n²). See this post for more details. You can just optimize it by stop point where substring lengths be smaller than current maximum deviation.

maxDeviation = 0;
n = strlen(str);
for i = 0 to n
{
  if(n-i < maxDeviation) break; //this is new stop point to improve 
  sub1 = substring(str,i,n);
  sub2 = substring(str,0,n-i); // you can use if(i!=0) to avoid duplication of first sentence 
  a = findMaxDeviation(sub1); // This is O(n)
  b = findMaxDeviation(sub2); // This is O(n)
  maxDeviation = max(a,b);
} 
print maxDeviation 

Pay attention to this line if(n-i < maxDeviation) break; because you cannot find a deviation more than maxDeviation in a string with length of smaller than maxDeviation.