Microsoft Online Assessment (OA) - Concatenated String Length with unique Characters

Given an Array A consisting of N Strings, calculate the length of the longest string S such that:

  • S is a concatenation of some of the Strings from A.
  • every letter in S is different.
  • N is [1..8]
  • A consists of lowercase English letters
  • Sum of length of strings in A does not exceed 100.

Example 1:

Input: ["co","dil","ity"]

Output: 5

Explanation:

String S could be codil, dilco, coity, ityco

Example 2:

Input: ["abc","kkk","def","csv"]

Output: 6

Explanation:

Strings S could be abcdef , defabc, defcsv , csvdef

Example 3:

Input: ["abc","ade","akl"]

Output: 0

Explanation:

impossible to concatenate as letters wont be unique.

Try it yourself

Implementation

1
1
from typing import List
2
2
3
3
def max_length(arr: List[str]) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
4
+
    dp = [set(x) for x in arr if len(set(x)) == len(x)]
5
-
    return 0
5
+
    for v in arr:
6
+
        a = set(v)
7
+
        if len(a) == len(v):
8
+
            for b in dp:
9
+
                if a & b:
10
+
                    continue
11
+
                dp.append(a | b)
12
+
    for x in arr:
13
+
        tmp = set(x)
14
+
        if tmp in dp:
15
+
            dp.remove(tmp)
16
+
    return max(len(x) for x in dp) if dp else 0
17
+
6
18
if __name__ == '__main__':
7
19
    arr = input().split()
8
20
    res = max_length(arr)
9
21
    print(res)