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
.
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.
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 sizeif (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 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 onbits
and ultimately also the value of its size – initially set to0
;res
will be our usual accumulator variable, storing the longest combination found so far, with initial value of0
;curr
andcurrBits
will store the values of our current string length and its composed bitmaks, respectively – both again pre-set to0
.
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 of0
andtmp
to help us in our parsing computations; - for each character
c
ins
, we will:- compute
tmp
as the1
raised to thec - 'a'
th power of2
, using bitwise shifting; - check if
bit & tmp
, which means we have already encountered a character likec
ins
, in which case we will:- reset
bit
to0
; break
out of the inner loop;
- reset
- alternatively, we will add
tmp
tobit
with a binary OR;
- compute
- finally, we will write
bit
intobits
and movepos
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 areturn
; - alternatively it will update
res
to be the maximum between its current value andcurr
; - another end case to consider now is when
start == pos
, meaning we are done parsing and we can justreturn
(a bit reduntant given the following loop, but I just find it cleaner); - we will then loop with
i
fromstart
topos
(excluded) and:- check if
bits[i]
is not0
and if we can add thei
th string tocurr
, not having duplicate characters (ie:(currBit & bits[i]) == 0
) and, if so:- increase
curr
byarr[i].size()
- add the bit flags in
bits[i]
tocurrBit
; - call the function recursively, passing
arr
again andi + 1
as a second parameter (ie: we will try to check all the possible permutations with other strings after thestart
th one); - decrease
curr
byarr[i].size()
- remove the bit flags in
bits[i]
tocurrBit
.
- increase
- check if
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
- 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