Microsoft Online Assessment 2021 Questions and Solution

Concatenated String Length with unique Characters

by

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 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 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;
    }
};

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions

Leave a Comment