Найдите все подстроки с четными единицами, обратная сторона которых также присутствует в данной строке.

Дана двоичная строка str . Задача состоит в том, чтобы найти размер множества (содержит уникальные подстроки) таких подстрок, что если существует подстрока (предположим A ) длины n с четным числом единиц, а также существует другая подстрока (предположим B ) того же длина n и четное количество единиц, и оно обратно A , то в наборе строк будет рассматриваться только A .

Примеры:

Input: str = “10101”
Output: 8
Explanation: All unique substrings of given string={1, 0, 10, 01, 101, 010, 1010, 0101, 10101}. 
In the above set (1010, 0101) is following the special property. 
Therefore, only 1010 will be considered in the given set. 
Updated Set = A = {1, 0, 10, 01, 101, 010, 1010, 10101}.
Length of A=8

Input: str = “10001”
Output: 11
Explanation: All unique substrings of given string={1, 0, 10, 01, 00, 100, 000, 001, 1000, 0001, 10001}. 
In the above set no string is following the special property. Length of Set=11

Подход: следуйте этим двум конкретным правилам, чтобы решить проблему:

• All pairwise strings not following special property should be identified uniquely.
• All pairwise strings following special property should be identified as one.

Итак, чтобы решить эту проблему, используйте набор List of integers, где каждый список будет содержать три переменные: {length, even, odd} . Кроме того, используйте переменную count , которая будет описывать количество единиц в подстроке. Здесь «длина» будет описывать длину подстроки. четные и нечетные переменные используются для описания количества единиц как четных или нечетных всякий раз, когда в подстроке встречается «0» . После этого добавьте его в набор подстрок, а затем напечатайте размер набора.

WHY DOES THIS WORK?

Consider a binary string with an even number of 1’s and whenever 0 is encountered in it, see how many 1’s occur in it before that 0 and if it is even increase the even variable count otherwise increase the odd variable count.

Suppose, when 0 is encountered in a substring and till that it has even 1’s then remaining would also be 1’s(because we have considered a string with even 1’s), similarly if we have odd 1’s till whenever we encounter 0 therefore remaining would also be odd 1’s. Therefore the reverse string would have the same parity(i.e count of 1’s as even or odd). That’s why it would not take the reverse string into consideration.

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

• Инициализируйте HashSet s[].
• Перебрать диапазон [0, str.length()) с помощью переменной i и выполнить следующие задачи:
  • Инициализируйте количество переменных, четных и нечетных , как 0 .
  • Перебрать диапазон [0, a.length()) с помощью переменной j и выполнить следующие задачи:
    • Если str[j] равно 1 , увеличьте значение count на 1.
    • В противном случае, если count%2 равно 0 , увеличьте значение четного на 1 , иначе значение нечетного на 1.
    • Инициализируйте переменную len как j-i+1.
    • Инициализировать новый ArrayList x[].
    • Добавьте значения {len,even,odd} в список ArrayList x[].
    • Добавьте x[] в HashSet s[].
• После выполнения вышеуказанных действий выведите в качестве ответа значение размера множества.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N*N), где N — длина строки.
Вспомогательное пространство: O(N)