using System;
using System.Collections.Generic;
using System.Linq;

namespace StringCombinations
{
  
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] words = new string[]
            {"rockstar","abc","Spain","rock","space","star","mars"};
            List<string> result = Combinations(words);
            foreach (var item in result)
            {
                Console.WriteLine($"{item} ");
            }
            
        }
        public static List<string> Combinations(string[] words)
        {
            HashSet<string> allwords = new HashSet<string>();
            List<string> result = new List<string>();

            foreach (var item in words)
            {
                if(!allwords.Contains(item))
                {
                    allwords.Add(item);
                }
            }
            //brute force solution : O(n square)
            /*
            for (int i = 0; i < words.Length; i++)
            {
                
                for (int j = 0; j < words.Length; j++)
                {
                    if (i != j && allwords.Contains(words[i] + words[j]))
                    {
                        result.Add(words[i]);
                        result.Add(words[j]);
                    }
                } 
            }
            */

            //Time complexity : O(n * m) -- where m is the largest element length
            for (int i = 0; i < words.Length; i++)
            {
                Char[] chars = words[i].ToCharArray();
                int j = 0; string s= string.Empty;
                
                while (j < chars.Length)
                {
                    s += chars[j];
                    if(words.Contains(s) && words[i] !=s)
                    {
                        result.Add(s);
                        s = string.Empty;
                    }
                    j++;
                }
               
            }
            return result;
           
        }
    }
}