Ответы Mail.ru: LeetCode трудности перевода (Variance)

Там же присутствует определение:

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same.

Есть строка, в которой n символов x, m символов y, k символов z.

max(n, m, k) - min(n, m, k) <-- это искомый variance.

И надо найти такую подстроку, в которой этот разброс максимален.

В лоб получается O(N²) для перебора подстрок, а каждую ещё нужно пройти и сложить в map или массив частоты букв, итого O(N³). Но чтобы не перебирать триллион символов, придётся, видимо, придумать асимптотику пошустрее.

P.S. И у меня такое чувство, будто я кого-то подсадил на онлайн игры или на героин.