Подсчет подстрок, в которых частота символа превышает частоту другого символа в строке

Для заданной строки S размера N , состоящей только из символов a , b и c , задача состоит в том, чтобы найти количество подстрок данной строки S , таких что частота символа a больше, чем частота символа c .

Примеры:

Input: S = “abcc”
Output: 2
Explanation:
Below are all the possible substrings of S(= “abcc”) having the frequency of the character greater than the character c:

1. “a”: The frequency of a and c is 1 and 0 respectively.
2. “ab”: The frequency of a and c is 1 and 0 respectively.

Therefore, the count of such substrings is 2.

Input: S = “abcabcabcaaaaabbbccccc”
Output: 148

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные подстроки заданной строки S и подсчитать те подстроки, в которых количество символов «a» больше, чем количество символов «c» . После проверки всех подстрок выведите значение общего количества в качестве результата.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью дерева сегментов. Идея состоит в том, чтобы сохранить разницу частот символов 'a' и 'c' для всех префиксов строки S в узле дерева отрезков. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, count значением 0 , чтобы сохранить разницу между частотами символов 'a' и 'c' .
• Инициализируйте переменную, скажем, ans равной 0 , чтобы сохранить количество подстрок, в которых частота символа 'a' больше, чем 'c' .
• Инициализируйте дерево сегментов со всеми 0 s, которые будут обновляться при обходе строки.
• Поскольку разница между частотами символов 'a' и 'c' может быть и отрицательной, все операции обновления дерева отрезков будут выполняться после добавления N к индексу, который необходимо обновить, чтобы избежать отрицательных индексов.
• Обновите значение индекса (0 + N) в дереве сегментов, поскольку начальное значение счетчика равно 0 .
• Пройдите по заданной строке S в диапазоне [0, N – 1] и выполните следующие шаги:
  • Если текущий символ 'a', то увеличьте счетчик на 1 . В противном случае, если текущий символ 'c', уменьшите счетчик на 1.
  • Выполните запрос к дереву сегментов, чтобы найти сумму всех значений, меньших count , поскольку все эти подстроки будут иметь частоту «a» больше, чем «c», и сохранят возвращаемое значение в переменной, например, val .
  • Добавьте значение val к переменной ans .
  • Обновите дерево сегментов, увеличив значение индекса (count + N) на 1 .
• После выполнения вышеуказанных шагов выведите значение ans как результирующее количество подстрок.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)