The problem
Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.
Return the maximum possible length of s.
Example test-cases
Example 1:
Input: arr = ["un","iq","ue"] Output: 4 Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique". Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"] Output: 6 Explanation: Possible solutions are "chaers" and "acters".
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"] Output: 26
Constraints
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i]contains only lower case English letters.
How to write the code
def maxLength(arr: List[str]) -> int:
result = [float('-inf')]
unique_char("", arr, 0, result)
if not result[0] == float('-inf'):
return result[0]
return 0
def unique_char(cur, arr, index, result):
# End of the array
if index == len(arr):
return
# Iterating from the current word to the end of the array
for index in range(index,len(arr)):
# If current word + next word have all unique characters
if len(set(cur + arr[index])) == len(list(cur + arr[index])):
# Compare the actual lenth with the previous max
result[0] = max(result[0],len(cur + arr[index]))
# Make a new call with concatenate words
unique_char(cur + arr[index], arr, index + 1,result)
