Проверить, можно ли разделить двоичную строку на непересекающиеся подпоследовательности, равные «010».

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

Примеры:

Input: S = “010100”
Output: Yes
Explanation: Partitioning the string in the manner 010100 to generate two subsequences equal to “010”.

Input: S = “010000”
Output: No

Подход: Идея основана на наблюдении, что данная двоичная строка не будет удовлетворять требуемому условию, если выполняется любое из следующих условий:

• Если в любой момент количество префиксов «1» больше, чем количество префиксов «0» .
• Если в любой момент количество суффиксов «1» больше, чем количество суффиксов «0» .
• Если количество «0» не равно удвоенному количеству «1» во всей строке.

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

1. Инициализируйте логическую переменную res как true , чтобы проверить, удовлетворяет ли строка S заданному условию или нет.
2. Создайте две переменные, count0 и count1 , чтобы хранить частоту 0 и 1 в строке S .
3. Пройдите строку S в диапазоне [0, N – 1], используя переменную i
   1. Если S[i] равно 1 , увеличьте значение count1 на 1 .
   2. В противном случае увеличьте значение count0 на 1 .
   3. Проверьте, является ли значение count1 > count0 , затем обновите res как false .
4. Проверьте, не равно ли значение count0 2 * count1 , затем обновите res как false .
5. Сбросьте значение count0 и count1 на 0 .
6. Пройдите по струне S в обратном направлении и повторите шаги с 3.1 по 3.3 .
7. Если значение res по-прежнему истинно , в качестве результата выведите «Да» , иначе выведите «Нет» .

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

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