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
2def maxLength(arr: List[str]) -> int:
3 maxlen = 0
4 unique = ['']
5
6 def isvalid(s):
7 return len(s) == len(set(s))
8
9 for word in arr:
10 for j in unique:
11 tmp = word + j
12 if isvalid(tmp):
13 unique.append(tmp)
14 maxlen = max(maxlen, len(tmp))
15
16 return maxlen
17
18if __name__ == "__main__":
19 word_list = input().split()
20 print(maxLength(word_list))
21
221import java.util.*;
2import java.util.stream.Collectors;
3class Solution {
4 public static int maxLength(String[] args) {
5 List<String> arr = Arrays.asList(args);
6 int maxLen = 0;
7 arr = arr.stream().filter(str-> isUnique(str)).collect(Collectors.toList());
8 Map<String,Integer> mem = new HashMap<>();
9 maxLen = dfs(arr, "", 0, maxLen, mem);
10 return maxLen;
11 }
12
13 private static int dfs(List<String> arr, String path, int i, int maxLen, Map<String, Integer> mem) {
14 if (mem.get(path) != null) return mem.get(path);
15 boolean pathIsUnique = isUnique(path);
16
17 if (pathIsUnique) {
18 maxLen = Math.max(path.length(), maxLen);
19 }
20
21 if (i == arr.size() || !pathIsUnique) {
22 mem.put(path, maxLen);
23 return maxLen;
24 }
25
26 for (int j = i; j < arr.size(); j++) {
27 maxLen = dfs(arr, path + arr.get(j), j + 1, maxLen, mem);
28 }
29
30 mem.put(path, maxLen);
31 return maxLen;
32 }
33
34 public static boolean isUnique(String str) {
35 char[] characters = str.toCharArray();
36 if (characters != null) Arrays.sort(characters);
37 for (int i = 0; i < characters.length - 1; i++) {
38 if (characters[i] == characters[i + 1]) return false;
39 }
40 return true;
41 }
42
43 public static void main(String[] args) {
44 Scanner scanner = new Scanner(System.in);
45 String[] wordList = scanner.nextLine().split(" ");
46 scanner.close();
47 System.out.println(maxLength(wordList));
48 }
49}
501const readline = require('readline');
2
3function maxLength(arr) {
4 let maxLen = 0;
5 arr = arr.filter(isUnique);
6 const mem = {};
7 maxLen = dfs(arr, "", 0, maxLen, mem);
8 function dfs(arr, path, i, maxLen, mem) {
9 if (mem[path]) return mem[path];
10 let pathIsUnique = isUnique(path);
11 if (pathIsUnique) {
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
23 mem[path] = maxLen;
24 return maxLen;
25 }
26
27 function isUnique(str) {
28 const set = new Set(str);
29 return set.size === str.length
30 }
31 return maxLen;
32}
33
34const rl = readline.createInterface(process.stdin);
35const inputs = [];
36rl.on('line', (input) => {
37 input !== '' ? inputs.push(input) : rl.close();
38}).on('close', () => {
39 const word_list = inputs[0].split(' ');
40 console.log(maxLength(word_list));
41});
42
43Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.