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

Даны две двоичные строки str1 и str2 длины N каждая. Задача состоит в том, чтобы разбить строки таким образом, чтобы сумма была максимальной при заданных условиях.

• Разделить обе строки в одной и той же позиции на подстроки одинаковой длины.
• Если обе подстроки содержат только 0, то значение добавляемой подстроки равно 1.
• Если обе подстроки содержат только 1, то значение добавляемой подстроки равно 0.
• Если обе подстроки содержат 0 и 1, то значение добавляемой подстроки равно 2.

Верните максимально возможную сумму.

Примеры:

Input: str1 = “0101000”, str2 = “1101100”
Output: 8
Explanation:
Split like this:
Take “0” from str1 and “1” from str2 -> 2
Take “10” from str1 and “10” from str2 -> 2
Take “1” from str1 and “1” from str2 -> 0
Take “0” from str1 and “1” from str2 -> 2
Take “0” from str1 and “0” from str2 -> 1
Take “0” from str1 and “0” from str2 -> 1
Sum is 2 + 2 + 0 + 2 + 1 + 1 => 8

Input: str1 = “01”, str2 = “01”
Output: 2

Подход : Эту проблему можно решить с помощью жадного подхода. Во-первых, возьмем некоторые из различных пар средних значений (0, 1), потому что они дают максимальное значение 2, или с парой различных значений с той же парой значений максимальное значение равно 2, поэтому нет никакой выгоды. затем попробуйте составить пару (0, 0) с (1, 1) или наоборот, чтобы максимизировать сумму.

• Инициализируйте MaxSum равным 0.
• Пройдитесь по струнам. Если Ai не равно Bi, увеличьте MaxSum на 2.
• Снова пройдитесь по строкам и попытайтесь соединить противоположное значение, означающее 0 с 1 или 1 с 0.
• Проверьте предыдущее и следующее значение строки, если оно противоположно, увеличьте MaxSum на 2.
• В противном случае, если пара состоит только из (0, 0), увеличьте MaxSum на 1.

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

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