Maximum Length of a Concatenated String with Unique Characters

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

Overview

Basic Data Structures

Basic Algorithms

Warm Up

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Interval

Two Sequences

Game Theory

0-1 Knapsack

Bitmask

Tree

Introduction

Generalized

Binary Search

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Greedy

Monotonic Stack

Line Sweep

Interval

Tree Traversal without Recursion

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Microsoft Online Assessment (OA) - Maximum Length of a Concatenated String with Unique Characters

Constraints:

Example 1:

Input: ["un","iq","ue"]

Output: 4

Explanation:

Example 2:

Input: ["cha","r","act","ers"]

Output: 6

Explanation:

Example 3:

Input: `["un","iq","ue"]`

Output: `4`

Input: `["cha","r","act","ers"]`

Output: `6`

Input: `["abcdefghijklmnopqrstuvwxyz"]`

Output: `26`