Максимизируйте значение двоичной строки в шагах K, выполнив XOR подстрок

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

Примеры :

Input: string S =”1010010″, K = 2
Output: “1111110”
Explanation:
In the first step, choose one substring as 1010010 and another as 101001, the XOR of these both strings will be 1111011.
In the second step, Choose one substring as 1111011 and another as 101, the XOR of these both strings will be 1111110, which is the maximum possible value you can get in K steps.

Input: string S =”11010″, K = 1
Output: “11111”
Explanation: Choose one substring as 11010 and another substring as 101, the XOR of these both strings will be 11111, which is the maximum possible value you can get in one step.

Подход : Данная проблема может быть решена с помощью следующей идеи.

Choose one substring as String S because it has maximum possible decimal value and other as the size – index of leftmost 0 because we have to maximise the size of substring and convert 0 to 1  and do this step K times.

Следуйте инструкциям, чтобы решить эту проблему:

• Подсчитайте количество 1 и 0 в строке.
• Если количество единиц равно длине строки, то может быть два случая
  • Если K кратно 2, т. е. даже мы можем выбрать подстроку '1' и выполнить над ней XOR четное число раз, то строка останется неизменной.
  • В противном случае мы выберем подстроку «1» и выполним операцию XOR, поэтому только младший бит будет изменен на «0».
• Если количество нулей равно длине строки, вернуть 0, так как 1 там нет.
• Возьмем одну подстроку как S , а другую (скажем, t ) — любую возможную подстроку размера N-idx , где idx — индекс крайнего левого 0.
• Возьмите XOR S и t , это максимально возможное значение.

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

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

Статьи по Теме:

• Введение в строки — учебные пособия по структурам данных и алгоритмам
• Введение в побитовые алгоритмы - учебные пособия по структурам данных и алгоритмам