# Concatenated String Length with unique Characters

Page Contents

Microsoft Online Assessment, Concatenated String Length with unique Characters

## Concatenated String Length with unique Characters

You are given an array of strings `arr`. A string `s` is formed by the concatenation of a subsequence of `arr` that has unique characters.

Return the maximum possible length of `s`.

subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:

```Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.
```

Example 2:

```Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
```

Example 3:

```Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.
```

Example 4:

```Input: arr = ["aa","bb"]
Output: 0
Explanation: Both strings in arr do not have unique characters, thus there are no valid concatenations.
```

Constraints:

• `1 <= arr.length <= 16`
• `1 <= arr[i].length <= 26`
• `arr[i]` contains only lowercase English letters.

## Solution

Program Python: Concatenated String Length with unique Characters in Python

Explanation

• Basic idea is to turn `arr` to `[(set(word), len(word))]` if word has no repeat letter
• Then we can use union (`&`) operation to check whether length of set after union is same as the sum of two size
• `if (union_len:=len(union:=arr[i] | cur_s)) == arr[i] + cur_l]`
• `if len(arr[i] | cur_s) == arr[i] + cur_l` same as above
• Due to the small data sacle (max length of `arr` is 16), use backtracking to try out all possbilities
• Maintain a maximum length with `ans`
```class Solution:
def maxLength(self, arr: List[str]) -> int:
arr = [(s, l) for word in arr if (l:=len(s:=set(word))) == len(word)]
ans, n = 0, len(arr)
def dfs(arr, cur_s, cur_l, idx):
nonlocal ans, n
ans = max(ans, cur_l)
if idx == n: return
[dfs(arr, union, union_len, i+1) for i in range(idx, n) if (union_len:=len(union:=arr[i] | cur_s)) == arr[i] + cur_l]
dfs(arr, set(), 0, 0)
return ans```

Program C++:

This kind of problems (at least for the relatively small amount of strings provided to us) can be tackled using a DFS approach; a backtracking on and on top of that, to avoid duplicate effort, we will also use a support array with bitmasks to tell us what characters are used in each string.

To do so, we will declare at class level a few support variables:

• `bits` is a pointer to the array we will create containing all the bitmasks equivalent to the provided strings;
• `pos` will be the pointer we will use to write on `bits` and ultimately also the value of its size – initially set to `0`;
• `res` will be our usual accumulator variable, storing the longest combination found so far, with initial value of `0`;
• `curr` and `currBits` will store the values of our current string length and its composed bitmaks, respectively – both again pre-set to `0`.

In the main function, we will first of all initialise `bits` to be an appropriately sized array and the we will parse each string `s` in `arr` and:

• declare `bit` with initial value of `0` and `tmp` to help us in our parsing computations;
• for each character `c` in `s`, we will:
• compute `tmp` as the `1` raised to the `c - 'a'`th power of `2`, using bitwise shifting;
• check if `bit & tmp`, which means we have already encountered a character like `c` in `s`, in which case we will:
• reset `bit` to `0`;
• `break` out of the inner loop;
• alternatively, we will add `tmp` to `bit` with a binary OR;
• finally, we will write `bit` into `bits` and move `pos` forward.

We can now move the action to our helper function dfs`, that we will call passing just`arr` (as a reference, of course).

This helper function will also take an extra parameter, `start`, that we will default to `0` and:

• check first of all if we already encountered the maximum obtainable value (`26`), in which case no point in continuining and we can stop the call here with a `return`;
• alternatively it will update `res` to be the maximum between its current value and `curr`;
• another end case to consider now is when `start == pos`, meaning we are done parsing and we can just `return` (a bit reduntant given the following loop, but I just find it cleaner);
• we will then loop with `i` from `start` to `pos` (excluded) and:
• check if `bits[i]` is not `0` and if we can add the `i`th string to `curr`, not having duplicate characters (ie: `(currBit & bits[i]) == 0`) and, if so:
• increase `curr` by `arr[i].size()`
• add the bit flags in `bits[i]` to `currBit`;
• call the function recursively, passing `arr` again and `i + 1` as a second parameter (ie: we will try to check all the possible permutations with other strings after the `start`th one);
• decrease `curr` by `arr[i].size()`
• remove the bit flags in `bits[i]` to `currBit`.

Once done, we can just `return` `res`.

```class Solution {
// support variables
int *bits, pos = 0, res = 0, curr = 0, currBit = 0;
void dfs(vector<string>& arr, int start = 0) {
// end case: max value achieved
if (res == 26) return;
res = max(res, curr);
// end case: no more combinations to check
if (start == pos) {
return;
}
for (int i = start; i < pos; i++) {
if (bits[i] && (currBit & bits[i]) == 0) {
// updating curr and currBits
curr += arr[i].size();
currBit ^= bits[i];
dfs(arr, i + 1);
// backtracking curr
curr -= arr[i].size();
currBit ^= bits[i];
}

}
}
public:
int maxLength(vector<string>& arr) {
// preparing bits
bits = new int[arr.size()];
for (auto &s: arr) {
int bit = 0, tmp;
for (char c: s) {
// updating the new bit flag
tmp = 1 << (c - 'a');
// checking if s has duplicate words
if (bit & tmp) {
bit = 0;
break;
}
bit |= tmp;
}
// writing bit into bits, if we found no duplicates
bits[pos++] = bit;
}
// comparing strings
dfs(arr);
return res;
}
};```

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions