Подсчитайте способы выбора трех индексов из двоичной строки с разными соседними цифрами

Для заданной двоичной строки S длины N задача состоит в том, чтобы найти количество способов выбрать три индекса так, что если они расположены в порядке возрастания индексов, никакие два соседних индекса не будут иметь одинаковое значение.

Примеры:

Input: S = “00110”
Output: 4
Explanation: Below are the possible valid indices:
=> {0, 2, 4} from “00110” forms “010”
=> {0, 3, 4} from “00110” forms “010”
=> {1, 2, 4} from “00110” forms “010”
=> {1, 3, 4} from “00110” forms “010”
No other selection is valid. Thus, there are 4 total ways.

 Input: S = “11100”
Output: 0

Подход, использующий технику PrefixSum.

Keep track of the number of zeros and ones on the left and right at any indices. At any index i, if the i^th digit is zero then for this index we can select (number of ones on the left * number of ones on the right). Similarly, if the digit is 1, check for the 0s n left and right. 

Keep adding the number of ways for every index in the result and finally return it.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Инициализируйте переменные totalZero и totalOne равными 0 , это будет отслеживать общее количество нулей и единиц в двоичном виде соответственно.
• Инициализируйте переменные currZero и currOne равными 0 , это будет отслеживать количество нулей и единиц до i- ^го индекса.
• Перебрать строку
  • Если текущая цифра равна нулю, увеличьте totalZero на 1
  • В противном случае увеличьте totalOne на 1
• Инициализировать переменную result , чтобы отслеживать ответ
• Перебрать строку
  • Если текущая цифра 0
    • Добавьте значение (количество единиц слева * количество единиц справа)
    • Увеличьте количество currZero на 1
  • В противном случае,
    • Добавьте значение (количество нулей слева * количество нулей справа)
    • Увеличьте количество currOnes на 1
• Наконец, верните результат .

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

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

Статьи по Теме:

• Введение в строки — учебные пособия по структурам данных и алгоритмам
• Массив сумм префиксов — реализация и приложения в соревновательном программировании