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 maxLength(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
+
    for v in arr:
6
+
        if len(a := set(v)) == len(v):
7
+
            for b in dp:
8
+
                if a & b:
9
+
                    continue
10
+
                dp.append(a | b)
11
+
    for x in arr:
12
+
        if (tmp := set(x)) in dp:
13
+
            dp.remove(tmp)
14
+
    return max(len(x) for x in dp) if dp else 0
15
+
5
16
if __name__ == "__main__":
6
17
    word_list = input().split()
7
18
    print(maxLength(word_list))