Skip to main content

1239. Maximum Length of a Concatenated String with Unique Characters

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

Python​

DFS (Timelimit Exceed)​

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        def dfs(i, result: str):
            if len(result) != len(set(result)):
                return 0

            ans = len(result)
            for j in range(i, len(arr)):
                ans = max(ans, dfs(i+1, result+arr[j]))
            return ans
        return dfs(0, "")

Compare duplicate with set length​

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        results = [""]
        ans = 0
        for word in arr:
            for i in range(len(results)):
                new_result = word + results[i]
                if len(new_result) != len(set(new_result)):
                    continue
                results.append(new_result)
                ans = max(ans, len(new_result))
        return ans