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 sub-sequence of arr which have unique characters. Return the maximum possible length of s.

Constraints:

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[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 wont 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
22
1import 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}
50
1const 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
43

Still not clear?Β SubmitΒ the part you don't understand to our editors.