HackerRank - string - Reverse Shuffle Merge - warm up practice - using stack - http://juliachencoding.blogspot.ca/2016/04/april-3-2016-httpsgist.html

reverseShuffleMerge_HackerRank_warmup.cs

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

namespace ReverseShuffleMerge_Warmup
{
    class Program
    {
        static void Main(string[] args)
        {
            //string input = Console.ReadLine();

            string[] testCases = new string[3]{"aaccbb","cacbab","baabcc"};

            List<string> outputStrs = new List<string>(); 
            foreach (string s in testCases)
            {
                string s2 = reverseShuffleMerge(s);

                outputStrs.Add(s2); 
            }

            string[] result = outputStrs.ToArray(); 
        }

        public static string reverseShuffleMerge(string input)
        {
            int[] skip = new int[26];
            int[] add = new int[26];

            for (int i = 0; i < input.Length; i++)
            {
                skip[input[i] - 'a']++;
            }

            for (int i = 0; i < 26; i++)
            {
                skip[i] /= 2;
                add[i] = skip[i];
            }

            Stack<char> stack = new Stack<char>();
            for (int i = input.Length - 1; i >= 0; i--)  // reverse 
            {
                char ch = input[i];

                // if stack is not empty, ch, wait to be added, 
                // top of stack - a char is bigger and can be skipped as well
                while (stack.Count > 0 && add[ch - 'a'] > 0 && stack.Peek() > ch && skip[stack.Peek() - 'a'] > 0)
                {
                    char chTop = stack.Pop();
                    add[chTop - 'a']++;
                    skip[chTop - 'a']--;
                }

                if (add[ch - 'a'] > 0)
                {
                    stack.Push(ch);
                    add[ch - 'a']--;
                }
                else
                {
                    skip[ch - 'a']--;
                }
            }

            string output = string.Empty;
            while (stack.Count > 0)
            {
                output = stack.Pop() + output;
            }

            return output; 
        }
    }
}