[Leetcode] 1239. 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

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이 주어질 때, 요소들을 합쳐서 만들 수 있는 가장 긴 문자열을 반환해라. 

문자열을 합쳤을 때 중복되는 문자가 존재하면 안된다.

 

Example 1:

Input	Output
arr = ["un","iq","ue"]	4
Explanation: All the valid concatenations are: - "" - "un" - "iq" - "ue" - "uniq" ("un" + "iq") - "ique" ("iq" + "ue") Maximum length is 4.

Example 2:

Input	Output
arr = ["cha","r","act","ers"]	6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").

Example 3:

Input	Output
arr = ["abcdefghijklmnopqrstuvwxyz"]	26
Explanation: The only string in arr has all 26 characters.

 

 

문제풀이 코드

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        result = [""]
        for i in range(len(arr)):
            if len(arr[i]) > len(set(arr[i])): continue
            for j in range(len(result)):
                temp = result[j] + arr[i]
                if len(temp) == len(set(temp)):
                    result.append(temp)
        result.sort(key=lambda x:len(x))
        return len(result[-1])

1. 빈 문자열이 들어있는 배열을 선언한다.

2. 주어진 arr을 순회하면서 현재 문자열에 중복된 문자열이 존재하면 continue

3. 그렇지않을 때, result를 순회하면서 result[j] + arr[i]를 해준다.

4. 만약 두 단어를 더했을 때 중복된 문자가 존재하면 result에 넣어주지않는다.

5. result를 문자열의 길이로 정렬하고 가장 긴 문자열을 반환한다.