Количество чередующихся подстрок из заданной двоичной строки

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

Примеры:

Input: S = “0010”
Output: 7
Explanation: 
All the substring of the string S are: {“0”, “00”, “001”, “0010”, “0”, “01”, “010”, “1”, “10”, “0”}
Strings that are alternating: {“0”, “0”, “01”, “010”, “1”, “10”, “0”}.
Hence, the answer is 7.

Input: S = “010”
Output: 6

Наивный подход: самый простой подход к решению этой проблемы состоит в том, чтобы сначала найдите все подстроки строки S , затем проверьте для каждой строки, чередуется она или нет.

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

Эффективный подход: эта проблема имеет свойство перекрывающихся подзадач и свойство оптимальной подструктуры. Так что эту проблему можно решить с помощью динамического программирования. Выполните следующие шаги, чтобы решить эту проблему:

• Объявите массив dp , где dp[i][j] хранит количество чередующихся строк, начинающихся с char i и находящихся в диапазоне [j, N-1] .
• Выполните итерацию в диапазоне [N-1, 0], используя переменную i , и выполните следующие шаги:
  • Если i равно N-1 , то если текущий символ равен '1' , тогда присвойте 1 dp[1][i] , иначе присвойте 1 dp[0][i] .
  • В противном случае, если текущий символ равен '0' , тогда обновите dp[0][i] до 1+dp[1][i+1] , в противном случае обновите dp[1][i] до 1+dp[0][ я+1].
• Инициализируйте переменную, скажем , как 0 , чтобы сохранить количество чередующихся подстрок.
• Выполните итерацию в диапазоне [0, N-1], используя переменную i , и выполните следующие шаги:
  • Обновить ответ как максимум dp[0][i] и dp[1][i].
• Наконец, в качестве ответа выведите полученное значение в ans .

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

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