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.

Answer 2

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

Answer 3

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;

Answer 4

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

Answer 5

Here is full answer with O(n)X26X26 time complexity, so it is linear time.

The essential algorithm is Kadane, like a maximum sum of subarray under dynamic programming hood.

In particular, we see the first letter of pair as any fix positive value, and the second as negative value, and continue to moving forward to get current cumulative sum of subarray, if it becomes negative, then reset as 0. and compare it to the best sum of other subarray.

The tricky corner case here to get result correct is using a flag to make sure you actual see the second letter in the string.

def kadane(s, c1, c2):

cur_num = 0
best_num = 0
flag = False
for l in s:
    if l == c1:
        a=1 
    elif l == c2:
        a =-1
        flag = True
    else:
        a=0
    cur_num = max(0, cur_num+a)
    best_num = max(best_num, cur_num)
    
return best_num if flag else 0

def maxdev(s):

char = ['a','b','c', 'd','e','f','g','h','i','j','k',
        'l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

max_dev = 0
for c1 in char:
    for c2 in char:
        if c1 == c2:
            continue
        cur_best = kadane(s, c1, c2)
        max_dev = max(cur_best, max_dev)
        
return max_dev 

s = 'aaabbbbbabcbbbaaaa'

maxdev(s) -> print out 8