[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/?envType=daily-question&envId=2024-01-23

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Maximum Length of a Concatenated String with Unique Characters

문제 유형 : 비트마스크, 다이나믹 프로그래밍, 재귀, 백트래킹

문제 난이도 : Medium

 

문제

You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.

Return the maximum possible length of s.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

 

당신은 문자열 배열 arr을 받는다. 문자열 s는 arr의 문자열들을 연결하여 만든 문자가 중복되지 않는 부분 문자열이다.

s의 최대 길이를 구하시오.

 

 

풀이

solve(index, str, res)를 이용했다.

index는 arr의 앞으로 넣을 인덱스, str은 현재 완성된 문자열, res는 최대 길이이다.

 

만약 문자열이 가능한 문자열이라면, res를 업데이트한다.

가능하지 않으면 재귀를 중단한다.

 

for문으로 index번부터 arr.size() 전까지 계속 solve(i, str+arr[i], res)를 재귀호출하여 백트래킹을 이용하여 답을 구한다.

 

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
    int n;
    vector<string> array;
public:
    bool isUnique(string &s) {
        set<char> st;
        for(const char ch : s) {
            if(st.find(ch) != st.end()) return false;
            st.insert(ch);
        }

        return true;
    }

    void solve(int index, string s, int& res) {
        if(isUnique(s)) res = max(res, (int)s.size());
        else return;

        for(int i = index; i < n; i++) {
            solve(i+1, s + array[i], res);
        }
    }

    int maxLength(vector<string>& arr) {
        n = arr.size();
        array = arr;
        int result = 0;
        solve(0, "", result);

        return result;
    }
};