leetcode medium : Maximum Length of a Concatenated String with Unique Characters

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

Maximum Length of a Concatenated String with Unique Characters - LeetCode

 

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        unique_sets = [set(element) for element in arr if len(element) == len(set(element))]
        
        all_possible_combinations = [set()]
        for single_set in unique_sets:
            apc_copy = all_possible_combinations.copy()
            
            for found_before in apc_copy:
                if not single_set & found_before:
                    all_possible_combinations.append(single_set | found_before)
        
        answer = max(len(comb) for comb in all_possible_combinations)
        return answer

 

지금까지 본 것들을 가지고 만들 수 있는 문자 조합  set를 계속 유지한다.

인풋 array를 처음부터 끝까지 하나씩 보면서 "지금까지 본 것들을 가지고 만들 수 있는 문자 조합  set"를 만들어나가면 된다.

상수 조건이 숫자가 매우 작은걸 보면 노가다(전문용어로 brute force 혹은 backtracking)문제인걸 쉽게 알 수 있다.