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

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

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

  • Минимальное количество подпоследовательностей, на которые можно разделить строку S , такое, что подпоследовательность не содержит соседних нулей или единиц.
  • Подпорядковый номер, которому принадлежит каждый символ строки S.

Если ответов много, выведите любой.

Примеры:

Input: S = “0011”, N = 4
Output: 
2
1 2 2 1
Explanation: 
There can be a minimum of 2 subsequences such that they donot have any adjacent zeroes or ones.
             Subsequence 1: “01”
             Subsequence 2: “01”
             Also, the first character of S(‘0’) belongs to subsequence 1(“01”)
             Second character of S(‘0’) belongs to subsequence 2(“01”)
             Third character of S(‘1’) belongs to subsequence 2(“01”)
             Fourth character of S(‘1’) belongs to subsequence 1(“01”)

Input: S = “1000110”, N = 7
Output:
3
1 1 2 3 3 2 2

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

  1. Создайте вектор an для хранения подпоследовательностей, которым принадлежит каждый символ строки S.
  2. Кроме того, создайте два вектора endZero и endOne для хранения подпоследовательностей, заканчивающихся на «0» и «1» соответственно.
  3. Поскольку в подпоследовательности не может быть смежных нулей или единиц. Следовательно, если символ равен «0» , следующим символом, который будет помещен в подпоследовательность, должен быть «1», и наоборот.
  4. Теперь, используя цикл, проходим по каждому символу S и проверяем, является ли он «0» или «1» . Кроме того, объявите переменную newSeq , которая представляет новую подпоследовательность, которая будет сформирована, если встречаются последовательные нули или единицы.
  5. Если символ равен '0' , проверьте, пуст ли вектор endOne или нет:
    • Если он пуст, то поместите newSeq в endZero .
    • В противном случае поместите последнюю подпоследовательность endOne в newSeq . Теперь эта последняя подпоследовательность endOne больше не заканчивается на «1» , так как к ней добавлен «0» . Таким образом, нажмите его в endZero .
  6. Точно так же, если символ в S равен '1' , выполняются те же шаги, что и выше, т. е. проверяется, является ли вектор endZero пустым или нет:
    • Если он пуст, добавьте newSeq в endOne .
    • В противном случае поместите последнюю подпоследовательность endZero в newSeq . Теперь эта последняя подпоследовательность endZero больше не заканчивается на «0» , так как к ней добавлена «1» . Таким образом, нажмите его в endOne .
  7. Затем вставьте newSeq в векторное сообщение .
  8. Повторите вышеуказанные шаги для каждого символа S .
  9. Минимальное количество подпоследовательностей будет дано суммой размеров endZero и endOne .
  10. Наконец, выведите минимальное количество подпоследовательностей и вектор ans .

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

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

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