Сложность: medium
Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.
Пример:
Input: arr = ["un","iq","ue"]
Output: 4
👨💻 Алгоритм:
1⃣Использование рекурсивного подхода:
Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов.
Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки.
Если не можем, пропускаем текущую строку и переходим к следующей.
2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.
3⃣Поиск максимальной длины:
На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины.
😎 Решение:
def maxLength(arr):
def is_unique(s):
return len(s) == len(set(s))
def backtrack(index, current):
if not is_unique(current):
return 0
max_length = len(current)
for i in range(index, len(arr)):
max_length = max(max_length, backtrack(i + 1, current + arr[i]))
return max_length
return backtrack(0, "")
Ставь 👍 и забирай 📚 Базу знаний