Минимизируйте затраты на преобразование данной строки в тип XYXY… или XXYY…

Дана двоичная строка s и массив ct[] четного размера. Задача состоит в том, чтобы минимизировать стоимость операций, чтобы:

• Преобразование строки s в строку типа XYXYXYXYXY … или XXYYXXYYXXYY …
• За одну операцию можно перевернуть i ^-й символ стоимостью ct[i] .

Примеры

Input: s = “1011” ct = {1, 2, 1, 3}
Output: 1
Explanation: Follow operations are performed to convert s to given format:
Flip the 0th bit from 1 to 0, the updated s = “0011” which is in the form XXYY. 
Hence, 1 is the answer which is minimum possible.

Input: “1010”
Output: 0
Explanation: The string is already in a given format. 

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

• Согласно задаче существует только четыре типа двоичных строк.
  • 010101010101…….
  • 101010101010…….
  • 001100110011……..
  • 110011001100……..
• Мы должны проверить только эти четыре разные строки.
• Передайте строку вместе со стоимостью и первыми четырьмя ожидаемыми символами.
• Если ожидаемые символы не совпадают с фактическими символами строки, добавьте стоимость, соответствующую i -му значению.
• Повторите процедуру для всех четырех ожидаемых последовательностей и выберите из них минимальную стоимость.

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

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