Microsoft Online Assessment (OA) - Maximum Length of a Concatenated String with Unique Characters

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.

Constraints:

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[i] contains only lower case English letters.

Example 1:

Input: ["un","iq","ue"]

Output: 4

Explanation:

All possible concatenations are "","un","iq","ue","uniq" and "ique".

Example 2:

Input: ["cha","r","act","ers"]

Output: 6

Explanation:

Possible solutions are "chaers" and "acters".

Example 3:

Input: ["abcdefghijklmnopqrstuvwxyz"]

Output: 26

Explanation:

impossible to concatenate as letters wont be unique.

Try it yourself

Implementation

1from typing import List
2def maxLength(arr: List[str]) -> int:
3      maxlen = 0
4      unique = ['']
5
6      def isvalid(s):
7          return len(s) == len(set(s))
8
9      for word in arr:
10          for j in unique:
11              tmp = word + j
12              if isvalid(tmp):
13                  unique.append(tmp)
14                  maxlen = max(maxlen, len(tmp))
15
16      return maxlen
17
18if __name__ == "__main__":
19    word_list = input().split()
20    print(maxLength(word_list))
21
22