Подстрока с наибольшей вариацией

Источник: https://leetcode.com/problems/substring-with-largest-variance/

Вариация строки - это разность между максимально встречающейся буквой и минимально встречающейся буквой в строке. Если строка содержит последовательность одной и той же буквы, то вариация = 0.

Дана строка s содержащая нижнестрочные буквы латинского алфавита только. Вернуть наибольшую вариацию среди всех подстрок строки s.

Подстрока - это непрерывная последовательность букв в строке.

Пример 1:

Дано: s = "aababbb"
Результат: 3
Объяснение:
Все возможные вариации среди соответствующих подстрок перечислены ниже:
- Вариация 0 для подстрок "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", и "bbb".
- Вариация 1 для подстрок "aab", "aba", "abb", "aabab", "ababb", "aababbb", и "bab".
- Вариация 2 для подстрок "aaba", "ababbb", "abbb", и "babb".
- Вариация 3 для подстроки "babbb".
Максимальная вариация = 3б мы это и возвращаем.

Пример 2:

Дано: s = "abcde"
Результат: 0
Объяснение:
Ни одна буква не встречается чаще 1 раза в s, поэтому в любой подстроке вариация = 0.

Идея решения

Временная сложность: O(26*26*n)

Для каждой буквы считаем количество ее вхождений в строку. Затем сравниваем частоты каждой пары букв: a(min freq) & b(max freq),
 

Находим подстроку где для текущей пары букв разница частот максимальна - это можно сделать алгоритмом Кадана.

 

Имплементация

class Solution {
    public int largestVariance(String s) {
        // считаем частоту вхождения букв
        int [] freq = new int[26];
        for(int i = 0 ; i < s.length() ; i++)
            freq[(int)(s.charAt(i) - 'a')]++;
        
        int maxVariance = 0;
        for(int a = 0 ; a < 26 ; a++){
            for(int b = 0 ; b < 26 ; b++){
                int remainingA = freq[a];
                int remainingB = freq[b];
                // пропускаем буквы, которые не входят в строку
                if(a == b || remainingA == 0 || remainingB == 0) continue;
                
				// run kadanes on each possible character pairs (A & B), occuring in string
                int currBFreq = 0, currAFreq = 0;
                for(int i = 0 ; i < s.length() ; i++){
                    int c =  (int)(s.charAt(i) - 'a');
                    
                    if(c == b) currBFreq++;
                    if(c == a) {
                        currAFreq++;
                        remainingA--;
                    }
                    
                    if(currAFreq > 0)
                        maxVariance = Math.max(maxVariance, currBFreq - currAFreq);
                    
                    if(currBFreq < currAFreq &&  remainingA >= 1){
                        currBFreq = 0;
                        currAFreq = 0;
                    }
                }
            }
        }
        
        return maxVariance;
    }
}