[LeetCode] Maximum Length of a Concatenated String with Unique Characters

Problem: 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.

Example:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Approach: Basically we need to apply backtracking here. We will try every valid combination and get the length of the largest valid combination here.

Implementation in C#:

    public int MaxLength(IList<string> arr) 

    {

        int maxLength = 0;

        int currLength = 0;

        int[] charsVisited = new int[26];

        MaxLengthRec(arr, 0, ref maxLength, currLength, charsVisited);

        return maxLength;

    }

    

    private void MaxLengthRec(

        IList<string> arr, 

        int currIndex, 

        ref int maxLength, 

        int currLength, 

        int[] charsVisited)

    {

        for (int i = 0; i < 26; ++i)

        {

            if (charsVisited[i] > 1)

            {

                return;

            }

        }

        maxLength = Math.Max(currLength, maxLength);                

        for (int i = currIndex; i < arr.Count; ++i)

        {

            foreach(char ch in arr[i])

            {

                ++charsVisited[ch - 'a'];

            }           

            currLength += arr[i].Length;

            MaxLengthRec(arr, i + 1, ref maxLength, currLength, charsVisited);

            currLength -= arr[i].Length;

            foreach(char ch in arr[i])

            {

                --charsVisited[ch - 'a'];

            }

        }

    }

Complexity: O(2^N)