5087. Letter Tile Possibilities

June 9, 2019

Introduction

It is the algorithm I like to learn as many solutions as I can. I also think about how to use this algorithm in mock interview for me to explore the algorithm as much as I can in future interviews on interviewing.io as a mock interviewer.

Case study

Here is one elegant solution I like to explore, learn and write one.
I wrote C# code based on the above post. Here is the link.

I also copy and paste the content here.

It is challenging job to understand the code and solution without a case stduy "AAB". I like to share C# code first with a solution. And then there is a post written with a case study to help to understand how to design, and what is "sum++" statement which refers to a substring in detail.

The solution code

Here is the elegant solution without tiles.

public class Solution {
    /// <summary>
        /// June 9, 2019
        /// study code:
        /// https://leetcode.com/problems/letter-tile-possibilities/discuss/308284/Concise-java-solution
        /// </summary>
        /// <param name="tiles"></param>
        /// <returns></returns>
        public int NumTilePossibilities(string tiles)
        {
            int[] count = new int[26];
            foreach (var item in tiles)
            {
                count[item - 'A']++;
            }

            return depthFirstSearch(count);
        }

        /// <summary>
        /// case study: "AAB"
        /// count: A -> 2, B->1
        /// length 1: "A", "B"
        /// length 2: 
        /// For "A":
        ///   count:  A->1, B->1
        ///   We can still pick either A, or B
        ///   So we have "AA,"AB"
        /// For "B":
        ///   count: A->2, B->0
        ///   We can only pick A
        ///   So we have "BA"
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        private static int depthFirstSearch(int[] numbers)
        {
            int sum = 0; 
            for(int i = 0; i < 26; i++)
            {
                if(numbers[i] == 0)
                {
                    continue;
                }

                sum++; // 
                numbers[i]--;
                sum += depthFirstSearch(numbers);
                numbers[i]++;
            }

            return sum; 
        }
}