Количество подстрок с равным соотношением 0 и 1 до i-го индекса в заданной двоичной строке

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

Примеры:

Input: S = “110001”
Output: {1, 2, 1, 1, 1, 2}
Explanation: The given string can be partitioned into the following equal substrings:

• Valid substrings upto index 0 : “1”, possible no. of substrings = 1
• Valid substrings upto index 1 : “1”, “B”, possible no. of substrings = 2
• Valid substrings upto index 2 : “110”, possible no. of substrings = 1
• Valid substrings upto index 3 : “1100”, possible no. of substrings = 1
• Valid substrings upto index 4 : “11000”, possible no. of substrings = 1
• Valid substrings upto index 5 : “1100”, “01”, possible no. of substrings = 2
   

Input: S = “010100001”
Output: {1, 1, 1, 2, 1, 2, 1, 1, 3}

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

1. Создайте два массива префиксов для вхождений 0 и 1 , скажем pre0[] и pre1[] соответственно.
2. Для каждого префикса пометьте его парой (a, b), где a = частота «0» и b = частота «1» в этом префиксе. Разделите a и b на gcd(a, b), чтобы получить простейшую форму.
3. Перебрать все префиксы и сохранить ответ для префикса как текущее количество вхождений этой пары.

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

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