You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

 Approach: Use hash

        public IList<int> FindSubstringWithConcatenation(string s, string[] words)

        {

            List<int> result = new List<int>();

            int numOfWords = words.Length;

            int sizeOfWord = words[0].Length;

            int sizeOfWords = sizeOfWord * numOfWords;

            if (s.Length < sizeOfWords)

            {

                return result;

            }

            Dictionary<string, int> hash = new Dictionary<string, int>();

            foreach(string word in words)

            {

                if (hash.ContainsKey(word))

                {

                    ++hash[word];

                }

                else

                {

                    hash[word] = 1;

                }

            }

            for (int i = 0; i <= s.Length - sizeOfWords; ++i)

            {

                Dictionary<string, int> tempHash = new Dictionary<string, int>(hash);

                int count = numOfWords;

                for(int j = i; j < i + sizeOfWords; j+= sizeOfWord)

                {

                    string str = s.Substring(j, sizeOfWord);

                    if (!tempHash.ContainsKey(str) || tempHash[str] == 0)

                    {

                        break;

                    }

                    --tempHash[str];

                    --count;

                }

                if(count == 0)

                {

                    result.Add(i);

                }

            }

            return result;

        }