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

---

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

---

문제

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.

---

조건

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i] contains only lowercase English letters.

---

내 풀이

uniques는 예시의 'uniq'나 'ique'처럼 중복되는 알파벳이 없는 단어를 모아두는 리스트다.

 

arr안에 있는 단어들을 앞에서부터 읽은 뒤, uniques의 모든 원소들과 붙여본다.

원소와 붙였을 때, len(temp) == len(set(temp))를 만족한다는 뜻은 중복되는 알파벳이 없다는 뜻이 되므로 uniques에 temp를 추가한다.

---

코드

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        uniques = ['']
        maxi = 0
        
        for word in arr:
            for idx in range(len(uniques)):
                temp = word + uniques[idx]
                
                if len(temp) == len(set(temp)):
                    uniques.append(temp)
                    maxi = max(maxi, len(temp))
        
        return maxi