Leetcode: Maximum Length of Concatenate String with Unique Characters

This is the most common Leetcode Question asked at Tesla, and frequently asked at Microsoft.

Given an array of Strings arr, String s is a concatenation of a sub-sequence of arr which have unique characters. Return the maximum possible length of s. 

Here are the examples:

Example 1:

Input: arr = ["un","iq","ue"]

Output: 4

Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".

Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]

Output: 6

Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]

Output: 26

 

Now you can either try all the combinations recursively, or you can use dynamic programming.

Let's go with dynamic programming. 

Here are the steps to go through.

1. Initialize the result res to include the case of the empty string "". The variable, Res, includes all the possible combinations we find when we iterate the input. 

2. Iterate through the input strings, but skip the words that have duplicate characters.

3. For each string, check if it's in conflict with the combination that was found. If they have intersection of characters, we skip it otherwise append this new combination to the result.

4. Finally return the maximum length of all the combinations.  

The Java implementation is as follows:

class Solution {

    private boolean isUnique(String str) {

        //more then number of letters in the alphabet

        if(str.length() > 26) return false; 

        boolean[] used = new boolean[26];

        char[] arr = str.toCharArray();

        for(char ch : arr) {

            //make sure no characters are used

            if(used[ch - 'a']) {

                return false;

            } else {

               //mark each used character

                used[ch - 'a'] = true;

            }

        }

        return true;

    }

    public int maxLength(List<String> arr) {

        List<String> res = new ArrayList<>(); 

        res.add(""); 

        for(String str : arr) {

            //skip any strings that are not unique

            if(!isUnique(str)) {

                continue;

            }

            List<String> resList = new ArrayList<>();

            

            for(String candidate : res) {

                String temp = candidate + str;

            //add any unique strings to the result list. 

                if(isUnique(temp)) {    

                    resList.add(temp);

                }

            }

        //add this to the result

        res.addAll(resList);

        }

        int ans = 0;

        //find the maximum length subsequence. 

        for(String str : res) {

            ans = Math.max(ans, str.length());

        }

        return ans;

    }

}