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

1from typing import List
2
3def max_length(arr: List[str]) -> int:
4    dp = [set(x) for x in arr if len(set(x)) == len(x)]
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
18if __name__ == '__main__':
19    arr = input().split()
20    res = max_length(arr)
21    print(res)
22