# Concatenated String Length with unique Characters

Page Contents

Microsoft Online Assessment, Concatenated String Length with unique Characters

## 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`.

Also See: Microsoft Online Assessment Questions and Solution

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 wont be unique.

## Solution

Program Python:

```from typing import List
def max_length(arr: List[str]) -> int:
dp = [set(x) for x in arr if len(set(x)) == len(x)]
for v in arr:
a = set(v)
if len(a) == len(v):
for b in dp:
if a & b:
continue
dp.append(a | b)
for x in arr:
tmp = set(x)
if tmp in dp:
dp.remove(tmp)
return max(len(x) for x in dp) if dp else 0
if __name__ == '__main__':
arr = input().split()
res = max_length(arr)
print(res)```

Program Java:

```import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Collectors;
class Solution {
public static boolean isUnique(String str) {
char[] characters = str.toCharArray();
if (characters != null) Arrays.sort(characters);
for (int i = 0; i < characters.length - 1; i++) {
if (characters[i] == characters[i + 1]) return false;
}
return true;
}
private static int dfs(List<String> arr, String path, int i, int maxLen, Map<String, Integer> mem) {
if (mem.get(path) != null) return mem.get(path);
boolean pathIsUnique = isUnique(path);
if (pathIsUnique && !arr.contains(path)) {
maxLen = Math.max(path.length(), maxLen);
}
if (i == arr.size() || !pathIsUnique) {
mem.put(path, maxLen);
return maxLen;
}
for (int j = i; j < arr.size(); j++) {
maxLen = dfs(arr, path + arr.get(j), j + 1, maxLen, mem);
}
mem.put(path, maxLen);
return maxLen;
}
public static int maxLength(List<String> args) {
int maxLen = 0;
List<String> arr = args.stream().filter(str-> isUnique(str)).collect(Collectors.toList());
Map<String,Integer> mem = new HashMap<>();
maxLen = dfs(arr, "", 0, maxLen, mem);
return maxLen;
}
public static List<String> splitWords(String s) {
return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<String> arr = splitWords(scanner.nextLine());
scanner.close();
int res = maxLength(arr);
System.out.println(res);
}
}```

Program C++:

```function maxLength(arr) {
let maxLen = 0;
const listOfStrs = [];
arr = arr.filter(isUnique);
const mem = {};
maxLen = dfs(arr, "", 0, maxLen, mem);
function dfs(arr, path, i, maxLen, mem) {
if (mem[path]) return mem[path];
const pathIsUnique = isUnique(path);
if (pathIsUnique && arr.indexOf(path)=== -1) {
maxLen = Math.max(path.length, maxLen);
}
if (i === arr.length || !pathIsUnique) {
mem[path] = maxLen;
return maxLen;
}
for (let j = i; j < arr.length; j++) {
maxLen = dfs(arr, path + arr[j], j + 1, maxLen, mem);
}
mem[path] = maxLen;
return maxLen;
}
function isUnique(str) {
const set = new Set(str);
return set.size === str.length
}
return maxLen;
}
function splitWords(s) {
return s == "" ? [] : s.split(' ');
}
function* main() {
const arr = splitWords(yield);
const res = maxLength(arr);
console.log(res);
}
class EOFError extends Error {}
{
const gen = main();
const next = (line) => gen.next(line).done && process.exit();
let buf = '';
next();
process.stdin.setEncoding('utf8');
process.stdin.on('data', (data) => {
const lines = (buf + data).split('\n');
buf = lines.pop();
lines.forEach(next);
});
process.stdin.on('end', () => {
buf && next(buf);
gen.throw(new EOFError());
});
}```

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions

### 2 thoughts on “Concatenated String Length with unique Characters”

1. Came in MasterCard online test