Подсчет 3 строк длины с заданными символами, содержащими не менее 2 разных символов

Даны три целых числа a , b и c , которые обозначают частоты трех разных символов « A », « B » и « C » соответственно и могут использоваться для формирования строк длины 3. Задача состоит в том, чтобы подсчитать общее количество возможных комбинаций A, B и C, которые образуют строку, содержащую как минимум 2 разных символа.

Пример:

Input: a = 2, b = 3, c = 3
Output: 2
Explanation: Possible strings which satisfies the given conditions are: {“ABC”, “ABC”}

Input: a = 5, b = 4, c = 3
Output: 4

Подход: Общее количество строк длины 3, которые могут быть сформированы с заданными частотами, равно (a+b+c)/3, при условии выбора любого символа для любой строки. Но поскольку требуются только строки с двумя разными символами, важно проверить, возможно это или нет. Чтобы проверить это:

1. Предположим, что все (a+b+c)/3 строки сформированы до двух позиций только с любым и все они имеют оставшееся место для заполнения.
2. Теперь до этого момента строки действительны, потому что:
   • Если строка содержит два разных символа, то она действительна.
   • Если в строке два одинаковых символа, ее можно сделать действительной, вставив другой символ.
3. Итак, общее количество различных символов, которые нам нужны, равно, скажем, count , где count = (a+b+c)/3 , при условии, что для каждой строки требуется один символ.
4. Таким образом, если сумма двух наименьших частот превышает count , то может быть сформировано (a+b+c)/3 количество строк. В противном случае это была бы сумма двух наименьших частот.

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

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