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!

What is the complexity of your brute force approach that you are thinking of? — ksohan, Jan 31 '22 at 04:41
You can do O(n^2) pretty easily, but i think it is harder to go below that considering there are O(n^2) substrings to consider. — Christian Sloper, Jan 31 '22 at 06:55

score 1 · Answer 1 · answered Jan 31 '22 at 14:26

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.

score 0 · Answer 2 · answered Jun 02 '22 at 20:52

    public static int getDev(Map<String, Integer> devEntries){
        List<Integer> entries = devEntries.entrySet().stream()
                .map(x->x.getValue())
                .collect(Collectors.toList());
        Comparator<Integer> collect = Comparator.naturalOrder();
        Collections.sort(entries,collect.reversed());
        return entries.get(0) - entries.get( entries.size()-1);
    }
    public static int getMaxFreqDeviation(String s, Set<Integer> deviations ) {
        for (int x=0;x<s.length();x++) {
            for (int g=x;g<s.length()+1;g++){
                String su =s.substring(x,g);
                Map<String, Integer> map = Arrays.asList(su.split(""))
                        .stream()
                        .collect(Collectors.groupingBy(v->v,Collectors.summingInt(v->1)));
                if (map.entrySet().size()==1){
                    deviations.add(abs(0));
                }else {
                    int devcount = getDev(map);
                    deviations.add(abs(devcount));
                }
            }

        }
        return deviations.stream().collect(Collectors.toList()).get(deviations.size()-1);
    }

    public static void main(String[] args){
         String se = "abcaba";
        Set<Integer> deviations = new TreeSet<>();
        int ans = getMaxFreqDeviation(se,deviations);
        System.out.println(ans);
    }
}

hey guys ,the code displayed is not properly formatted , still learning howto do stuff around here,any way ,but it works — ajadi olatunde, Jun 02 '22 at 20:56
As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). — NoeOnJupiter, Jun 03 '22 at 13:36

Find maximum deviation of all substrings

2 Answers2