Количество подстрок из заданных троичных строк, содержащих символы хотя бы один раз

Дана строка str размера N , состоящая только из 0 , 1 и 2 , задача состоит в том, чтобы найти количество подстрок, состоящих из символов 0 , 1 и 2 хотя бы один раз.

Примеры:

Input: str = “0122”
Output: 2
Explanation:
There exists 2 substrings such that the substrings has characters 0, 1, 2 at least once is “012” and “0122”. Therefore, the count of substrings is 2.

Input: S = “00021”
Output: 3

Подход: данная проблема может быть решена с использованием метода скользящего окна, идея состоит в том, чтобы создать массив частот размером 3 , который содержит вхождения 0 , 1 и 2 . Пройдите по заданной строке и соответствующим образом обновите массив freq , если все 3 индекса в массиве больше нуля, тогда подсчитайте минимум из них и увеличьте его до переменной count . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массив freq[] размером 3 для хранения частоты всех элементов в массиве.
• Инициализируйте переменную count как 0 , чтобы сохранить ответ, и i как 0 , чтобы сохранить левый указатель.
• Перебрать диапазон [0, N), используя переменную j , и выполнить следующие задачи:
  • Увеличить частоту текущего символа str[ I ] в массиве freq[] на 1.
  • Пройдите в цикле while до тех пор, пока freq[0], freq[1] и freq[2] не станут больше 0, уменьшите частоту символа в i-й позиции на 1 и увеличьте значение i на 1.
  • Добавьте значение i к переменной count.
• После выполнения вышеуказанных шагов выведите значение count в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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