Сложность: medium
Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.
Пример:
Input: arr = ["un","iq","ue"]
Output: 4
👨💻 Алгоритм:
1⃣Использование рекурсивного подхода:
Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов.
Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки.
Если не можем, пропускаем текущую строку и переходим к следующей.
2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.
3⃣Поиск максимальной длины:
На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины.
😎 Решение:
var maxLength = function(arr) {
const isUnique = s => new Set(s).size === s.length;
const backtrack = (index, current) => {
if (!isUnique(current)) return 0;
let maxLength = current.length;
for (let i = index; i < arr.length; i++) {
maxLength = Math.max(maxLength, backtrack(i + 1, current + arr[i]));
}
return maxLength;
};
return backtrack(0, "");
};Ставь 👍 и забирай 📚 Базу знаний