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 subsequence of arr which has unique characters.
Return the maximum possible length of s.
Constraints:
1 <= arr.length <= 161 <= arr[i].length <= 26arr[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 won't be unique.
Try it yourself
Implementation
1from typing import List
2
3def max_length(arr: List[str]) -> int:
4 maxlen = 0
5 unique = [""]
6
7 def isvalid(s: str) -> bool:
8 return len(s) == len(set(s))
9
10 for word in arr:
11 for j in unique:
12 tmp = word + j
13 if isvalid(tmp):
14 unique.append(tmp)
15 maxlen = max(maxlen, len(tmp))
16
17 return maxlen
18
19if __name__ == "__main__":
20 arr = input().split()
21 res = max_length(arr)
22 print(res)
231import 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 return true;
16 }
17
18 private static int dfs(List<String> arr, String path, int i, int maxLen, Map<String, Integer> mem) {
19 if (mem.get(path) != null) return mem.get(path);
20 boolean pathIsUnique = isUnique(path);
21
22 if (pathIsUnique) {
23 maxLen = Math.max(path.length(), maxLen);
24 }
25
26 if (i == arr.size() || !pathIsUnique) {
27 mem.put(path, maxLen);
28 return maxLen;
29 }
30
31 for (int j = i; j < arr.size(); j++) {
32 maxLen = dfs(arr, path + arr.get(j), j + 1, maxLen, mem);
33 }
34
35 mem.put(path, maxLen);
36 return maxLen;
37 }
38
39 public static int maxLength(List<String> arr) {
40 int maxLen = 0;
41 arr = arr.stream().filter(str -> isUnique(str)).collect(Collectors.toList());
42 Map<String, Integer> mem = new HashMap<>();
43 maxLen = dfs(arr, "", 0, maxLen, mem);
44 return maxLen;
45 }
46
47 public static List<String> splitWords(String s) {
48 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
49 }
50
51 public static void main(String[] args) {
52 Scanner scanner = new Scanner(System.in);
53 List<String> arr = splitWords(scanner.nextLine());
54 scanner.close();
55 int res = maxLength(arr);
56 System.out.println(res);
57 }
58}
591"use strict";
2
3function isUnique(str) {
4 const set = new Set(str);
5 return set.size === str.length;
6}
7
8function maxLength(arr) {
9 let maxLen = 0;
10 arr = arr.filter(isUnique);
11 const mem = {};
12
13 function dfs(arr, path, i, maxLen, mem) {
14 if (mem[path]) return mem[path];
15 const pathIsUnique = isUnique(path);
16 if (pathIsUnique) {
17 maxLen = Math.max(path.length, maxLen);
18 }
19 if (i === arr.length || !pathIsUnique) {
20 mem[path] = maxLen;
21 return maxLen;
22 }
23 for (let j = i; j < arr.length; j++) {
24 maxLen = dfs(arr, path + arr[j], j + 1, maxLen, mem);
25 }
26
27 mem[path] = maxLen;
28 return maxLen;
29 }
30
31 maxLen = dfs(arr, "", 0, maxLen, mem);
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