1239. Maximum Length of a Concatenated String with Unique Characters

Here is the link.

C# A solution with readable code using DFS

It is the algorithm which can be solved using depth first search. I like to practice and also make the code easy to write and readable.

Here are highlights:

1. Design depth first search and recursive function with four arguments;
2. default empty string is considered as a unique string with my defined isUnique function;
3. Depth first search algorithm is to go through all possible paths starting from a list from 0 to length - 1;
4. isUnique function is implemented to compare a hashSet's count to string's length.

Follow up
I did not come out the solution in weekly contest 160 on Oct. 26, 2019. It is a simple brute force DFS solution. I will look into how to improve performance on weekly contest.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1239_maximujm_length
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// Oct. 29, 2019
        /// study code
        /// 1239 Maximum length of concatenated string with unique characters
        /// My ideal solution is to write a DFS solution which can easily be understandable, 
        /// and also it can be written in less than 15 minutes. 
        /// </summary>
        /// <param name="arr"></param>
        /// <returns></returns>
        public int MaxLength(IList<string> arr)
        {
            var maxLength = 0;

            runDFS(arr, ref maxLength, 0, "");

            return maxLength; 
        }

        private static void runDFS(IList<string> array, ref int maxLength, int index, string path)
        {
            if (!isUnique(path))
            {
                return;
            }

            var current = path.Length;
            maxLength = current > maxLength ? current : maxLength;

            for (int i = index; i < array.Count; i++)
            {
                runDFS(array, ref maxLength, i + 1, path + array[i]);
            }
        }

        private static bool isUnique(string path)
        {
            var hashSet = new HashSet<char>(path);
            return path.Length == hashSet.Count(); 
        }
    }
}