Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.

Пример:

Input: arr = ["un","iq","ue"]
Output: 4

👨‍💻 Алгоритм:

1⃣Использование рекурсивного подхода:
Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов.
Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки.
Если не можем, пропускаем текущую строку и переходим к следующей.

2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.

3⃣Поиск максимальной длины:
На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины.

😎 Решение:

import java.util.*;

public class Solution {
    public int maxLength(List<String> arr) {
        return backtrack(arr, 0, "");
    }

    private boolean isUnique(String s) {
        Set<Character> charSet = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (!charSet.add(c)) {
                return false;
            }
        }
        return true;
    }

    private int backtrack(List<String> arr, int index, String current) {
        if (!isUnique(current)) return 0;
        int maxLength = current.length();
        for (int i = index; i < arr.size(); i++) {
            maxLength = Math.max(maxLength, backtrack(arr, i + 1, current + arr.get(i)));
        }
        return maxLength;
    }
}

Ставь 👍 и забирай 📚 Базу знаний