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

1
1
from typing import List
2
2
def maxLength(arr: List[str]) -> int:
3
-
    # WRITE YOUR BRILLIANT CODE HERE
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
+
4
18
if __name__ == "__main__":
5
19
    word_list = input().split()
6
20
    print(maxLength(word_list))