Concatenated String Length with unique Characters

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”

Leave a Comment