Leetcode - Maximum Length of a Concatenated String with Unique Characters

Question

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.

This is a tesla question

• Uses backtracking, you could also use a bitmap but idk how (counting from 0 bitwise and ANDing?)

Solution

• $O\left(2^n\cdot m\right)$
  • 2^decisions multiplied by avg length of string

class Solution:
	def maxLength(self, arr: List[str]) -> int:
		chars = set()
		def overlap(chars, s):
			c = Counter(chars) + Counter(s)
			return max(c.values()) > 1
 
		def backtrack(i):
			if i == len(arr):
				return len(chars)
			res = 0
			if not overlap(chars, arr[i]):
				for c in arr[i]:
					chars.add(c)
				res = backtrack(i + 1)
			for c in arr[i]:
				chars.remove(c)
			return max(res, backtrack(i + 1))
		return backtrack(0)