# Concatenated String Length with unique Characters Microsoft OA 2023

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

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.

Also See: Amazon OA Online Assessment 2023 Questions and Answers

### SOLUTION

Program: Concatenated String Length with unique Characters Solution 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][0] | cur_s)) == arr[i][1] + cur_l]
• if len(arr[i][0] | cur_s) == arr[i][1] + 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][0] | cur_s)) == arr[i][1] + cur_l]
dfs(arr, set(), 0, 0)
return ans``````

Program: Concatenated String Length with unique Characters Solution in 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 justarr` (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 ith 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 startth 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;
}
};``````