Количество групп последовательных единиц в заданной двоичной строке

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

Примеры:

Input: S = “100110111”, N = 9
Output: 3
Explanation: 
The following groups are of 1s only:

1. Group over the range [0, 0] which is equal to “1”.
2. Group over the range [3, 4] which is equal to “11”.
3. Group over the range [6, 8] which is equal to “111”.

Therefore, there are a total of 3 groups of 1s only.

Input: S = “0101”
Output: 2

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

• Инициализируйте переменную, скажем, count как 0 , которая хранит количество подстрок 1 s в S .
• Инициализируйте стек, скажем, st для хранения подстроки только до индекса 1 s.
• Переберите символы строки S , используя переменную i , и выполните следующие действия:
  • Если текущий символ равен 1 , поместите 1 в стек st .
  • В противном случае, если st не пусто, увеличить count на 1 . Остальное Ясная ул .
• Если st не пусто, увеличить count на 1, т.е. если есть суффикс 1s.
• Наконец, распечатайте полученное общее количество .

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

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