Maximum Length of a Concatenated String with Unique Characters

문자열이 담긴 벡터 데이터를 받는데, 이 문자열들을 조합하여 가장 긴 문자열의 길이를 구하는 문제이다.

단 문자열에 조건이 있는데 알파벳은 중복되어 사용되면 안 된다.

class Solution {
public:
    int maxLength(vector<string>& arr) {

        vector<bool> used(26, false);
        int maxLength{0};
        DFS(-1, "", used, arr, maxLength);
        return maxLength;        
    }

    void DFS(int index, string concat, vector<bool> &used, vector<string>& arr, int &maxLength)
    {
        int arrSize = arr.size();

        maxLength = std::max((int)concat.size(), maxLength);
        if (index == arrSize)
        {
            return;
        }

        for (int i = index + 1; i < arrSize; i++)
        {
            bool noOverLap{true};
            int subsequenceSize = arr[i].size();

            vector<bool> tempUsed(used);
            for (int j = 0; j < subsequenceSize; j++)
            {
                if (tempUsed[arr[i][j] - 'a'])
                {
                    noOverLap = false;
                    break;
                }
                tempUsed[arr[i][j] - 'a'] = true;
            }

            if (noOverLap)
            {
                DFS(i, concat + arr[i], tempUsed, arr, maxLength);
            }
        }
    }
};