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:
Sis a concatenation of some of the Strings fromA.- every letter in
Sis different. Nis[1..8]Aconsists of lowercase English letters- Sum of length of strings in
Adoes not exceed100.
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 won't 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)
221import java.util.Arrays;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5import java.util.Scanner;
6import java.util.stream.Collectors;
7
8class Solution {
9 public static boolean isUnique(String str) {
10 char[] characters = str.toCharArray();
11 if (characters != null) Arrays.sort(characters);
12 for (int i = 0; i < characters.length - 1; i++) {
13 if (characters[i] == characters[i + 1]) return false;
14 }
15
16 return true;
17 }
18
19 private static int dfs(List<String> arr, String path, int i, int maxLen, Map<String, Integer> mem) {
20 if (mem.get(path) != null) return mem.get(path);
21 boolean pathIsUnique = isUnique(path);
22
23 if (pathIsUnique && !arr.contains(path)) {
24 maxLen = Math.max(path.length(), maxLen);
25 }
26
27 if (i == arr.size() || !pathIsUnique) {
28 mem.put(path, maxLen);
29 return maxLen;
30 }
31
32 for (int j = i; j < arr.size(); j++) {
33 maxLen = dfs(arr, path + arr.get(j), j + 1, maxLen, mem);
34 }
35
36 mem.put(path, maxLen);
37 return maxLen;
38 }
39
40 public static int maxLength(List<String> args) {
41 int maxLen = 0;
42 List<String> arr = args.stream().filter(Solution::isUnique).collect(Collectors.toList());
43 Map<String, Integer> mem = new HashMap<>();
44 maxLen = dfs(arr, "", 0, maxLen, mem);
45 return maxLen;
46 }
47
48 public static List<String> splitWords(String s) {
49 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
50 }
51
52 public static void main(String[] args) {
53 Scanner scanner = new Scanner(System.in);
54 List<String> arr = splitWords(scanner.nextLine());
55 scanner.close();
56 int res = maxLength(arr);
57 System.out.println(res);
58 }
59}
601"use strict";
2
3function isUnique(str) {
4 const set = new Set(str);
5 return set.size === str.length;
6}
7
8function dfs(arr, path, i, maxLen, mem) {
9 if (mem[path]) return mem[path];
10 const pathIsUnique = isUnique(path);
11 if (pathIsUnique && arr.indexOf(path) === -1) {
12 maxLen = Math.max(path.length, maxLen);
13 }
14 if (i === arr.length || !pathIsUnique) {
15 mem[path] = maxLen;
16 return maxLen;
17 }
18 for (let j = i; j < arr.length; j++) {
19 maxLen = dfs(arr, path + arr[j], j + 1, maxLen, mem);
20 }
21
22 mem[path] = maxLen;
23 return maxLen;
24}
25
26function maxLength(arr) {
27 let maxLen = 0;
28 arr = arr.filter(isUnique);
29 const mem = {};
30 maxLen = dfs(arr, "", 0, maxLen, mem);
31
32 return maxLen;
33}
34
35function splitWords(s) {
36 return s === "" ? [] : s.split(" ");
37}
38
39function* main() {
40 const arr = splitWords(yield);
41 const res = maxLength(arr);
42 console.log(res);
43}
44
45class EOFError extends Error {}
46{
47 const gen = main();
48 const next = (line) => gen.next(line).done && process.exit();
49 let buf = "";
50 next();
51 process.stdin.setEncoding("utf8");
52 process.stdin.on("data", (data) => {
53 const lines = (buf + data).split("\n");
54 buf = lines.pop();
55 lines.forEach(next);
56 });
57 process.stdin.on("end", () => {
58 buf && next(buf);
59 gen.throw(new EOFError());
60 });
61}
62