Get the Maximum Length of a Concatenated String With Unique Characters in Python

  • Home /
  • Blog Posts /
  • Get the Maximum Length of a Concatenated String with Unique Characters in Python

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


  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[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):

  # 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)