Contents
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.
- 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:
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;
}
};
Microsoft Online Assessment 2023 Questions List
- Maximal Network Rank Solution
- Min Deletions To Obtain String in Right Format
- Day of week that is K days later Solution
- Minimum Adjacent Swaps to Make Palindrome Solution
- Lexicographically Smallest String
- Longest Substring Without Two Contiguous Occurrences of Letter
- String Without 3 Identical Consecutive Letters
- Microsoft OA Longest Semi-Alternating Substring
- Microsoft OA Min Steps to Make Piles Equal Height
- Max Inserts to Obtain String Without 3 Consecutive ‘a’
- Concatenated String Length with unique Characters
- Largest K such that both K and -K exist in array
- Microsoft OA Min Adj Swaps to Group Red Balls
- Maximum Length of a Concatenated String with Unique Characters
- Microsoft OA Unique Integers That Sum Up To 0
- Find N Unique Integers Sum up to Zero
- Microsoft OA Particle Velocity Solution
- Microsoft OA Arithmetic Slices Solution
- Microsoft OA Widest Path Without Trees Solution
- Microsoft OA Jump Game Solution
- Microsoft OA Fair Indexes Solution