Сгенерировать двоичную строку с равным количеством 01 и 10 подпоследовательностей

Опубликовано: 19 Сентября, 2022

Для заданного целого числа N (N > 2) задача состоит в том, чтобы сгенерировать двоичную строку размера N , состоящую из равного количества подпоследовательностей « 10 » и « 01 », а также строка должна содержать по крайней мере один «0» и один « 1'

Примечание. Если существует несколько таких строк, выведите любую.

Примеры:

Input: 4
Output: 0110
Explanation : Here, 0110 string consists equal count of ’01’ and ’10’
subsequence and it consists at least one occurrence  of 0 as well as 1.

Input: 3
Output: 010
Explanation : Here, 010 string consists equal count of ’01’ and ’10’ 
subsequence and it consists at least one occurrence  of 0 as well as 1.

Наивный подход:

The idea is to generate every possible binary string(string which consists of only 0’s and 1’s) and find a substring with equal number of ’01’ and ’10’ subsequence.

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

Эффективный подход: для решения проблемы следуйте следующим наблюдениям:

Case 1 (If N is even): Then add 1s at N/2 and (N/2 – 1) index, and add 0s to the rest of the string. So the count of ’10’ and ’01’ will be same which is equal to 2*(N/2 – 1) = (N – 2) and string also consists of at least once occurrence of 0 and 1.

For example:

  • If N = 4, that means N is even, then add 1 at index N/2 =2 and (N/2)-1 = 1 . 
  • And add 0s at remaining positions from 0 to 3 .
  • Hence, string is “0110”.

Case 2 (If N is odd): Then add 1s at middle and add 0s to the rest of the string. So the count of ’10’ and ’01’ is same which is equal to N/2 and string also consists at least once occurrence of 0 and 1.

For example:

  • If N=3, that means N is odd then add 1 at index N/2=1.
  • And add 0s at remaining positions from 0 to 2.
  • Hence, string is “010”.

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

  • Возьмите пустую строку s .
  • Теперь проверьте, является ли N четным или нечетным:
    • Если N четно, выполните итерацию от 0 до N – 1 и добавьте «1» только к индексу N/2 и (N/2 – 1) и «0» к другим индексам строки.
    • Если N нечетно, выполните итерацию от 0 до N-1 и добавьте «1» только к индексу N/2 и «0» ко всем остальным индексам строки.
  • Теперь верните построенную строку.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ