Concatenated String Length with unique Characters

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

• 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