Concatenated String Length with unique Characters Microsoft OA 2023

Table of 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.

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

Leave a Comment

seven + one =