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

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

Пример:

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

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MaxLength(IList<string> arr) {
        return Backtrack(arr, 0, "");
    }

    private bool IsUnique(string s) {
        HashSet<char> charSet = new HashSet<char>(s);
        return charSet.Count == s.Length;
    }

    private int Backtrack(IList<string> arr, int index, string current) {
        if (!IsUnique(current)) return 0;
        int maxLength = current.Length;
        for (int i = index; i < arr.Count; i++) {
            maxLength = Math.Max(maxLength, Backtrack(arr, i + 1, current + arr[i]));
        }
        return maxLength;
    }
}

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