Find maximum deviation of all substrings

user_2566694 0
Viewed 12232

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!

word-frequency hashmap algorithm string
4 Answers

For finding all substrings you have to consider O(n2). 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.

user_25274580 
    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);
    }
}
user_117091190

I faced a similar question in a test and I used c#, although I failed during the challenge but picked it up to solve the next day. I came about something like the below.

var holdDict = new Dictionary<char, int>(); var sArray = s.ToCharArray();

var currentCharCount = 1;

//Add the first element
holdDict.Add(sArray[0],1);

for (int i = 1; i < s.Length-1; i++)
{
    if (sArray[i] == sArray[i - 1])
    {
        currentCharCount += 1;
    }
    else
    {
        currentCharCount = 1;
    }
    holdDict.TryGetValue(sArray[i], out var keyValue);

    if (keyValue < currentCharCount) holdDict[sArray[i]] = currentCharCount;

}

var myQueue = new PriorityQueue<string, int>();
foreach (var rec in holdDict)
{
    myQueue.Enqueue($"{rec.Key}#{rec.Value}", rec.Value);
}

int highest = 0, lowest = 0, queueCount=myQueue.Count;
while (myQueue.Count > 0)
{
    int currentValue = int.Parse(myQueue.Peek().Split('#')[1]);

    if (myQueue.Count == queueCount) lowest = currentValue;

    highest = currentValue;
    myQueue.Dequeue();
}

return highest - lowest;
user_69079170

O(n) algo (26*26*N)

import string

def maxSubarray(s, ch1, ch2):
    """Find the largest sum of any contiguous subarray."""
    """From https://en.wikipedia.org/wiki/Maximum_subarray_problem"""
    best_sum = 0
    current_sum = 0
    for x in s:
        if x == ch1:
            x = 1
        elif x == ch2:
            x = -1
        else:
            x = 0
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

def findMaxDiv(s):
    '''Algo from https://discuss.codechef.com/t/help-coding-strings/99427/4'''
    maxDiv = 0
    for ch1 in string.ascii_lowercase:
        for ch2 in string.ascii_lowercase:
            if ch1 == ch2:
                continue

            curDiv = maxSubarray(s, ch1, ch2)
            if curDiv > maxDiv:
                maxDiv = curDiv

    return maxDiv
user_28942850
Related