Leetcode 1360 Solution

This article provides solution to leetcode question 1360 (maximum-length-of-a-concatenated-string-with-unique-characters)
Categories:
Tags:
Access this page by simply typing in "lcs 1360" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def maxLength(self, arr) -> int:
        def get_bitmap(s):
            res = 0
            for ch in s:
                bit = 1 << (ord(ch) - ord('a'))
                if (res & bit) != 0:
                    return None, None
                res |= bit



            return res, len(s)



        bitmaps = []
        for ele in arr:
            bitmap, cnt = get_bitmap(ele)
            if bitmap is None:
                continue
            bitmaps.append((bitmap, cnt))



        ans = 0



        def dfs(curr, i, cnt):
            nonlocal bitmaps
            nonlocal ans



            if i == len(bitmaps):
                ans = max(ans, cnt)
                return



            bitmap, local_cnt = bitmaps[i]
            if (bitmap & curr) == 0:
                dfs(bitmap | curr, i + 1, cnt + local_cnt)



            dfs(curr, i + 1, cnt)



        dfs(0, 0, 0)
        return ans