Задача с собеседования в Zalando

Даны три целых числа: x, y и z.
У вас есть x строк, равных "AA", y строк, равных "BB", и z строк, равных "AB". Вы хотите выбрать некоторое (возможно, все или ни одной) количество из этих строк и объединить их в некотором порядке, чтобы сформировать новую строку. Эта новая строка не должна содержать подстрок "AAA" или "BBB".
Известно, что подстрока - это непрерывная непустая последовательность символов внутри строки.
Верните максимально возможную длину новой строки.

Пример 1:
Input: x = 2, y = 5, z = 1
Output: 12
Объяснение: мы можем объединить строки "BB", "AA", "BB", "AA", "BB" и "AB" в таком порядке. Тогда наша новая строка будет "BBAABBAABBAB".
Длина этой строки равна 12, и мы можем показать, что невозможно сформировать строку большей длины.

Пример 2:
Input: x = 3, y = 2, z = 2
Output: 14
Объяснение: мы можем объединить строки "AB", "AB", "AA", "BB", "AA", "BB" и "AA" в таком порядке. Тогда наша новая строка будет "ABABAABBAABBAA".
Длина этой строки равна 14, и мы можем показать, что невозможно сформировать строку большей длины.

Ограничения:
1 <= x, y, z <= 50

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задачу можно решить с помощью жадного алгоритма или более элегантно - с помощью выведения математической формулы, считающей длину строки. Используем второй способ:

Последовательности, которые мы можем соединять:
"AB" + "AA" = "ABAA"
"BB" + "AB" = "BBAB"
"AA" + "BB" = "AABB"

И те, которые НЕ можем:
"AA" + "AA" = "AAAA"
"BB" + "BB" = "BBBB"
"AA" + "AB" = "AAAB"

Строка "AB" самая безопасная и может использоваться для разбиения других последовательностей.
Если у нас равное количество строк "AA" и "BB" (x == y), то, чтобы высчитать максимальную длину строки нужно: сложить количество строк "AA", "BB" и "AB" и умножить сумму на 2 (по 2 символа в каждой строке).

Если же количество строк "AA" и "BB" различно, то: чередуем "AA" и "BB" столько раз, сколько можно. Далее, когда один из типов строк заканчивается, добавляем ещё одну строку противоположного типа. Так мы максимально продляем строку и не допускаем образования запрещённой подстроки.
Для наглядности:
Если x < y: ...AA + BB + AB - и дальше можем продолжать строку только типом "AB".
Если x > y: ...BB + AA или ...BB + AB + AA - и далее строку продолжать невозможно.

Определим, строк какого типа у нас меньше ("AA" или "BB"). Сформулируем формулу: мы используем все строки безопасного типа "AB" (по 2 символа в каждой: z * 2), также все строки того типа, которого у нас меньше (m * 2 символа), и строки противоположного типа в количестве, равном количеству строк менее частого типа + 1 ((m + 1)* 2 символа).

Сложность
O(1) - по времени
O(1) - по памяти

Код
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
m = min(x, y)
if x == y:
return 2 * (x + y + z)
else:
return 2 * m + (m + 1) * 2 + 2 * z

@algoses