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 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)
22
1import 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(str-> isUnique(str)).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}
60
1function maxLength(arr) {
2    let maxLen = 0;
3    const listOfStrs = [];
4    arr = arr.filter(isUnique);
5    const mem = {};
6    maxLen = dfs(arr, "", 0, maxLen, mem);
7    function dfs(arr, path, i, maxLen, mem) {
8        if (mem[path]) return mem[path];
9        const pathIsUnique = isUnique(path);
10        if (pathIsUnique && arr.indexOf(path)=== -1) {
11            maxLen = Math.max(path.length, maxLen);
12        }
13        if (i === arr.length || !pathIsUnique) {
14            mem[path] = maxLen;
15            return maxLen;
16        }
17        for (let j = i; j < arr.length; j++) {
18            maxLen = dfs(arr, path + arr[j], j + 1, maxLen, mem);
19        }
20
21
22        mem[path] = maxLen;
23        return maxLen;
24    }
25
26    function isUnique(str) {
27        const set = new Set(str);
28        return set.size === str.length
29    }
30    return maxLen;
31}
32
33function splitWords(s) {
34    return s == "" ? [] : s.split(' ');
35}
36
37function* main() {
38    const arr = splitWords(yield);
39    const res = maxLength(arr);
40    console.log(res);
41}
42
43class EOFError extends Error {}
44{
45    const gen = main();
46    const next = (line) => gen.next(line).done && process.exit();
47    let buf = '';
48    next();
49    process.stdin.setEncoding('utf8');
50    process.stdin.on('data', (data) => {
51        const lines = (buf + data).split('\n');
52        buf = lines.pop();
53        lines.forEach(next);
54    });
55    process.stdin.on('end', () => {
56        buf && next(buf);
57        gen.throw(new EOFError());
58    });
59}
60

Got 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.

←
↑TA 👨‍🏫